package com.my.leetcode;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Leetcode String problems
 *
 */
public class StringProblems
{
    public static void main( String[] args )
    {
        StringProblems stringProblems = new StringProblems();

        Date date = new Date();

        System.out.println(date.getTime());

        /*System.out.println(stringProblems.longestPalindrome("======" + "aabbbcd"));
        System.out.println(stringProblems.lengthOfLongestSubstringII("pwwkew"));
        System.out.println(stringProblems.lengthOfLongestSubstringII("bbbbb"));
        System.out.println(stringProblems.lengthOfLongestSubstringII("abcabcaa"));*/
        //System.out.println(stringProblems.lengthOfLongestSubstringII("abcabcaa"));
        //System.out.println(stringProblems.generateParenthesis(3));

        String s = "1201234";
        String s2 = "10011";
       // System.out.println(stringProblems.numDecodings91(s));
        System.out.println(stringProblems.numDecodings91(s2));
    }


    /**
     * @author zlx
     * @Description 91. 解码方法
     * 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
     *
     * 'A' -> 1
     * 'B' -> 2
     * ...
     * 'Z' -> 26
     * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
     *
     * "AAJF" ，将消息分组为 (1 1 10 6)
     * "KJF" ，将消息分组为 (11 10 6)
     * 注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
     *
     * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
     *
     * 题目数据保证答案肯定是一个 32 位 的整数。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "12"
     * 输出：2
     * 解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
     * 示例 2：
     *
     * 输入：s = "226"
     * 输出：3
     * 解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
     * 示例 3：
     *
     * 输入：s = "0"
     * 输出：0
     * 解释：没有字符映射到以 0 开头的数字。
     * 含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
     * 由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
     * 示例 4：
     *
     * 输入：s = "06"
     * 输出：0
     * 解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 100
     * s 只包含数字，并且可能包含前导零。
     *
     * 解题思路： 动态规划求解， dp[i] 表示字符串从0到i有多少中组成方式；
     *                       有一个字符构成，s[i] != 0， dp[i] = dp[i-1]
     *                       2个字符构成，s[i-1]s[i] >=10 && s[i-1]s[i] <= 26 dp[i] = dp[i-2]
     *
     * @Date 4/22/21
     * @Param [s]
     * @return int
     **/
    public int numDecodings91(String s) {

        if(s == null || s.length() <= 0 || s.charAt(0) == '0'){
            return 0;
        }
        int [] dp = new int[s.length()];
        dp[0] = 1;
        for(int i = 1;i < s.length();i++){

            int preVal = s.charAt(i-1) - '0';
            int curVal = s.charAt(i) - '0';
            if(preVal != 1 && preVal != 2 && curVal == 0){
                return 0;
            }
            int val = preVal * 10 + curVal;
            if(preVal >= 1 && preVal < 3 && curVal == 0){
                if(i >= 2){
                    dp[i] = dp[i-2];
                }else{
                    dp[i] = 1;
                }
            }
            else if(preVal >= 1 && preVal < 3 && val > 10 && val <= 26){
                if(i >= 2)
                    dp[i] = dp[i-1] + dp[i-2];
                else
                    dp[i] = dp[i-1] + 1;
            }else{
                dp[i] = dp[i-1];
            }
        }

        return dp[s.length() - 1];
    }


    public int numDecodings91II(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }



    /**
     * @author zlx
     * @Description 424. 替换后的最长重复字符
     * 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
     *
     * 注意：字符串长度 和 k 不会超过 104。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "ABAB", k = 2
     * 输出：4
     * 解释：用两个'A'替换为两个'B',反之亦然。
     * 示例 2：
     *
     * 输入：s = "AABABBA", k = 1
     * 输出：4
     * 解释：
     * 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
     * 子串 "BBBB" 有最长重复字母, 答案为 4。
     *
     * 解题思路：方法：双指针（滑动窗口）
     * 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
     * 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
     * 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。
     *
     * @Date 4/4/21
     * @Param [s, k]
     * @return int
     **/
    public int characterReplacement(String s, int k) {


        if(s == null){
            return 0;
        }

        if(s.length() <= 1 || s.length() <= k){
            return s.length();
        }

        int [] characterCount = new int[26];
        int maxCount = 1;
        int res = 0;
        int left = 0, right = 0, n = s.length();
        while (right < n){

            int index = s.charAt(right) - 'A';
            characterCount[index] ++;
            maxCount = Math.max(maxCount, characterCount[index]);
            right ++;
            if(right - left > maxCount + k){

                characterCount[s.charAt(left)] --;
                left ++;
            }

            res = Math.max(res, right - left);
        }

        return res;
    }

    /**
     * @author zlx
     * @Description 442. 数组中重复的数据
     * 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
     *
     * 找到所有出现两次的元素。
     *
     * 你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
     *
     * 示例：
     *
     * 输入:
     * [4,3,2,7,8,2,3,1]
     *
     * 输出:
     * [2,3]
     *
     * 解题思路：利用索引号+取反
     * 利用索引号，因为所有数值是在1~n之间，那么我们可以用索引0表示数字1，索引1表示数字2...。
     * 每遍历一次数组，就将此数的index对应的原来正的数字取负，若此index对应的数为负，
     * 则说明已出现过；并且取负之后仍然可以取到正确的位置值（取绝对值即可）。
     * @Date 4/4/21
     * @Param [nums]
     * @return java.util.List<java.lang.Integer>
     **/
    public List<Integer> findDuplicates(int[] nums) {

        List<Integer> res = new ArrayList<>();
        if(nums == null || nums.length<= 1){
            return res;
        }

        for(Integer num : nums){

            int index = Math.abs(num) - 1;
            if(nums[index] < 0){
                res.add(Math.abs(num));
            }
            nums[index] = -nums[index];
        }
        //System.out.println(Arrays.toString(nums));
        return res;

    }

    /**
     * @author zlx
     * @Description 838. 推多米诺 middle
     * 一行中有 N 张多米诺骨牌，我们将每张多米诺骨牌垂直竖立。
     *
     * 在开始时，我们同时把一些多米诺骨牌向左或向右推。
     *
     *
     *
     * 每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
     *
     * 同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
     *
     * 如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
     *
     * 就这个问题而言，我们会认为正在下降的多米诺骨牌不会对其它正在下降或已经下降的多米诺骨牌施加额外的力。
     *
     * 给定表示初始状态的字符串 "S" 。如果第 i 张多米诺骨牌被推向左边，则 S[i] = 'L'；如果第 i 张多米诺骨牌被推向右边，则 S[i] = 'R'；如果第 i 张多米诺骨牌没有被推动，则 S[i] = '.'。
     *
     * 返回表示最终状态的字符串。
     *
     * 示例 1：
     *
     * 输入：".L.R...LR..L.."
     * 输出："LL.RR.LLRRLL.."
     * 示例 2：
     *
     * 输入："RR.L"
     * 输出："RR.L"
     * 说明：第一张多米诺骨牌没有给第二张施加额外的力。
     * 提示：
     *
     * 0 <= N <= 10^5
     * 表示多米诺骨牌状态的字符串只含有 'L'，'R'; 以及 '.';
     * @Date 3/23/21
     * @Param [dominoes]
     * @return java.lang.String
     **/
    public String pushDominoes(String dominoes) {

        char [] charArray = dominoes.toCharArray();
        int [] forces = new int[charArray.length];
        int n = charArray.length;
        int force = 0;
        //向右推，最大的力为数组的长度，力度递减
        for(int i = 0;i < charArray.length;i++){

            if(charArray[i] == 'R'){
                force = n;
            }else if(charArray[i] == 'L'){
                force = 0;
            }else{
                force = Math.max(force - 1, 0);
            }
            forces[i] = force;
        }

        //向左推，最大的力为数组的长度，力度递减
        force = 0;
        for(int j = n-1;j >= 0;j--){

            if(charArray[j] == 'L'){
                force = n;
            }else if(charArray[j] == 'R'){
                force = 0;
            }else{
                force = Math.max(force - 1, 0);
            }
            //力道差 = 右推力度-左推力度 > 0 ,右倒； 力道差<0 左倒； 力道差=0 力道平衡
            forces[j] = forces[j] - force;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < n;i++){

            if(forces[i] > 0){
                sb.append('R');
            }else if(forces[i] < 0){
                sb.append('L');
            }else{
                sb.append('.');
            }
        }
        return sb.toString();

    }


    public String[] permutation(String s) {

        char [] chars = s.toCharArray();
        Arrays.sort(chars);
        res = new ArrayList<>();
        charList = new ArrayList<>();
        boolean [] flags = new boolean[s.length()];
        //dfs(chars, flags);
        sb = new StringBuilder();
        dfs2(chars, flags);
        return  res.stream().toArray(String[]::new);
    }


    List<String> res = new ArrayList<>();
    List<Character> charList = new ArrayList<>();



    /**
     * @author zlx
     * @Description 此dfs方法会超时，需要考虑剪纸
     * @Date 3/19/21
     * @Param [chars, flags]
     * @return void
     **/
    public void dfs(char[] chars, boolean [] flags){

        if(charList.size() >= chars.length){
            String tmp = charList.stream().map(e->e.toString()).reduce((acc, e) -> acc  + e).get();
            if(!res.contains(tmp)){
                res.add(tmp);
            }
            return ;
        }

        for(int i = 0;i < chars.length;i++){
            if(!flags[i]) {
                charList.add(chars[i]);
                flags[i] = true;
                dfs(chars, flags);
                flags[i] = false;
                charList.remove(charList.size() - 1);
            }

        }
    }

    /**
     * @author zlx
     * @Description //TODO
     * @Date 3/19/21
     * @Param [chars, flags]
     * @return void
     **/

    StringBuilder sb = new StringBuilder();
    public void dfs2(char[] chars, boolean [] flags){

        if(sb.length() >= chars.length){
            res.add(sb.toString());
            return ;
        }

        for(int i = 0;i < chars.length;i++){
            if(!flags[i]) {
                if(i > 0 && chars[i-1] == chars[i] && !flags[i-1]){
                    continue;
                }
                sb.append(chars[i]);
                flags[i] = true;
                dfs2(chars, flags);
                flags[i] = false;
                sb.deleteCharAt(sb.length() - 1);
            }

        }
    }


    /**
     * @author zlx
     * @Description 115. 不同的子序列
     * 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
     *
     * 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
     *
     * 题目数据保证答案符合 32 位带符号整数范围。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "rabbbit", t = "rabbit"
     * 输出：3
     * 解释：
     * 如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
     * (上箭头符号 ^ 表示选取的字母)
     * rabbbit
     * ^^^^ ^^
     * rabbbit
     * ^^ ^^^^
     * rabbbit
     * ^^^ ^^^
     * 示例 2：
     *
     * 输入：s = "babgbag", t = "bag"
     * 输出：5
     * 解释：
     * 如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
     * (上箭头符号 ^ 表示选取的字母)
     * babgbag
     * ^^ ^
     * babgbag
     * ^^    ^
     * babgbag
     * ^    ^^
     * babgbag
     *   ^  ^^
     * babgbag
     *     ^^^
     *
     *
     * 提示：
     *
     * 0 <= s.length, t.length <= 1000
     * s 和 t 由英文字母组成
     *
     * 解题思路： 动态规划求解， dp[i][j] 表示s[i:] s从i到最后，包含t[j:] t从j到最后，子序列的个数
     * @Date 3/17/21
     * @Param [s, t]
     * @return int
     **/
    public int numDistinct(String s, String t) {

        /*list = new ArrayList<>();
        count = 0;
        dfsDistinct(s, t, 0);
        return count;*/

        int m = s.length(), n = t.length();
        int [][] dp = new int[m+1][n+1];
        for(int i = 0;i <= m;i++){
            dp[i][n] = 1;
        }

        for(int i = m - 1;i >= 0;i--){

            for(int j = n-1;j >= 0;j--){

                if(s.charAt(i) == t.charAt(j)){

                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
                }else{
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }


    List<Character> list = new ArrayList<>();
    int count = 0;
    /**
     * @author zlx
     * @Description dfs求解方法正确，但是在leetcode上跑会超出时间限制
     * @Date 3/17/21
     * @Param [s, t, start]
     * @return void
     **/
    public void dfsDistinct(String s, String t, int start){

        if(list.size() == t.length()){
            count++;
            return ;
        }

        for(int i = start;i < s.length();i++){

            if(s.charAt(i) == t.charAt(list.size())){
                list.add(s.charAt(i));
                dfsDistinct(s, t, i + 1);
                if(list.size() > 0){
                    list.remove(list.size() - 1);
                }
            }
        }
    }



    /**
     * @author zlx
     * @Description 721. 账户合并 middle
     * 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。
     *
     * 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。
     *
     * 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。账户本身可以以任意顺序返回。
     *
     *
     *
     * 示例 1：
     *
     * 输入：
     * accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
     * 输出：
     * [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
     * 解释：
     * 第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
     * 第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
     * 可以以任何顺序返回这些列表，例如答案 [['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
     * ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']] 也是正确的。
     *
     *
     * 提示：
     *
     * accounts的长度将在[1，1000]的范围内。
     * accounts[i]的长度将在[1，10]的范围内。
     * accounts[i][j]的长度将在[1，30]的范围内。
     * @Date 1/18/21
     * @Param [accounts]
     * @return java.util.List<java.util.List<java.lang.String>>
     **/
    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        Map<String, Integer> emailToIndex = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        int emailsCount = 0;
        for(List<String> account : accounts){
            String name = account.get(0);
            int size = account.size();
            for(int i = 1;i < size;i++){
                String email = account.get(i);
                if(!emailToIndex.containsKey(email)){
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email,  name);
                }
            }
        }

        UnionSearch unionSearch = new UnionSearch(emailsCount);

        //构建并查集
        for(List<String> account : accounts){
            String firstEmail = account.get(1);
            int firstIndex = emailToIndex.get(firstEmail);
            for(int i = 2;i < account.size();i++){
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                unionSearch.union(firstIndex, nextIndex);
            }
        }
        //构建同一个email的并集
        Map<Integer, List<String>> indexToEmails = new HashMap<>();
        for(Map.Entry<String, Integer> entry : emailToIndex.entrySet()){

            String email = entry.getKey();
            Integer index = entry.getValue();

            Integer unionIndex = unionSearch.find(index);
            List<String> emails = indexToEmails.getOrDefault(unionIndex, new ArrayList<>());
            emails.add(email);

            indexToEmails.put(unionIndex, emails);
        }
        //构建结果
        List<List<String>> res = new ArrayList<>();
        for(List<String> emails : indexToEmails.values()){

            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<>();
            account.add(name);
            account.addAll(emails);
            res.add(account);
        }
        return  res;
    }



    public class UnionSearch{

        private int [] parents;

        public UnionSearch(int n){
            parents = new int[n];
            for(int i = 0;i < n;i++){
                parents[i] = i;
            }
        }

        public void union(int x, int y){
            parents[find(y)] = find(x);
        }


        public int find(int y){

            if(parents[y] != y){
                parents[y] = find(parents[y]);
            }

            return parents[y];
        }

        @Override
        public String toString() {
            return "UnionSearch{" +
                    "parents=" + Arrays.toString(parents) +
                    '}';
        }
    }


    /**
     * @author zlx
     * @Description 1202. 交换字符串中的元素
     * 给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
     *
     * 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
     *
     * 返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
     *
     *
     *
     * 示例 1:
     *
     * 输入：s = "dcab", pairs = [[0,3],[1,2]]
     * 输出："bacd"
     * 解释：
     * 交换 s[0] 和 s[3], s = "bcad"
     * 交换 s[1] 和 s[2], s = "bacd"
     * 示例 2：
     *
     * 输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
     * 输出："abcd"
     * 解释：
     * 交换 s[0] 和 s[3], s = "bcad"
     * 交换 s[0] 和 s[2], s = "acbd"
     * 交换 s[1] 和 s[2], s = "abcd"
     * 示例 3：
     *
     * 输入：s = "cba", pairs = [[0,1],[1,2]]
     * 输出："abc"
     * 解释：
     * 交换 s[0] 和 s[1], s = "bca"
     * 交换 s[1] 和 s[2], s = "bac"
     * 交换 s[0] 和 s[1], s = "abc"
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 10^5
     * 0 <= pairs.length <= 10^5
     * 0 <= pairs[i][0], pairs[i][1] < s.length
     * s 中只含有小写英文字母
     *
     * 解题思路： 1、查并集 [0,1]可互换， [0,2]可互换，等与[0,1,2] 三个可任意互换
     *           2、分别根据并集中的字符串进行字典排序
     *           3、将字点排序放回对应的位置
     * @Date 1/11/21
     * @Param [s, pairs]
     * @return java.lang.String
     **/
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {

        if(pairs.size() <= 0){
            return s;
        }
        //1.构建并集
        UnionFind unionFind = new UnionFind(s.length());
        for(List<Integer> pair : pairs){
            unionFind.union(pair.get(0), pair.get(1));
        }
        //2.构建映射关系
        char [] charArray = s.toCharArray();
        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
        for(int i = 0;i < s.length();i++) {
            int root = unionFind.find(i);
            map.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);
        }

        // 第 3 步：重组字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            int root = unionFind.find(i);
            stringBuilder.append(map.get(root).poll());
        }
        return stringBuilder.toString();
    }


    private class UnionFind{


        private int [] parent;

        private int [] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for(int i = 0;i < n;i++){

                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        public void union(int x, int y){

            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY){
                return ;
            }

            if (rank[rootX] == rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度仅加了 1
                rank[rootY]++;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度不变
            } else {
                // 同理，此时以 rootX 为根结点的树的高度不变
                parent[rootY] = rootX;
            }

        }

        public int find(int x){
            if(x != parent[x]){
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }




    /**
     * @author zlx
     * @Description 830. 较大分组的位置
     * 在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。
     *
     * 例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。
     *
     * 分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。
     *
     * 我们称所有包含大于或等于三个连续字符的分组为 较大分组 。
     *
     * 找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "abbxxxxzzy"
     * 输出：[[3,6]]
     * 解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。
     * 示例 2：
     *
     * 输入：s = "abc"
     * 输出：[]
     * 解释："a","b" 和 "c" 均不是符合要求的较大分组。
     * 示例 3：
     *
     * 输入：s = "abcdddeeeeaabbbcd"
     * 输出：[[3,5],[6,9],[12,14]]
     * 解释：较大分组为 "ddd", "eeee" 和 "bbb"
     * 示例 4：
     *
     * 输入：s = "aba"
     * 输出：[]
     *
     * 提示：
     *
     * 1 <= s.length <= 1000
     * s 仅含小写英文字母
     * @Date 1/5/21
     * @Param [s]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> largeGroupPositions(String s) {

        List<List<Integer>> res = new ArrayList<>();
        if(s == null || s.length() <= 2){
            return res;
        }
        int start = 0, end = 1;
        while (start < s.length() && end < s.length()){

            if(s.charAt(start) == s.charAt(end)){
                end ++;
            }else{
                if((end - start) >= 3){
                    res.add(Arrays.asList(start, end - 1));
                }
                start = end;
                end ++;
            }
        }
        if(end - start >= 3){
            res.add(Arrays.asList(start, end - 1));
        }
        System.out.println("start:" + start + "  end:  "+ end);
        return res;
    }


    public boolean wordPattern(String pattern, String s) {

        if(pattern == null || pattern.length() <= 0){
            return false;
        }

        String [] arrs = s.split(" ");
        if(arrs.length != pattern.length()){
            return false;
        }

        Map<Character, String> map = new HashMap<>();
        //防止出现abba dog dog dog dog 返回值为true
        List<String> list = new ArrayList<>();
        for(int i = 0;i < pattern.length();i++){
            char tmp = pattern.charAt(i);
            if((map.containsKey(tmp) && !map.get(tmp).equals(arrs[i])) || (!map.containsKey(tmp) && list.contains(arrs[i]))){
                return false;
            }else if(!map.containsKey(tmp) && (!list.contains(arrs[i]) || list.isEmpty())){
                map.put(tmp, arrs[i]);
                list.add(arrs[i]);
            }
        }
        return true;
    }


    /**
     * @author zlx
     * @Description 649. Dota2 参议院 middle
     * Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)
     *
     * Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：
     *
     * 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
     *
     * 宣布胜利：如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

     * 给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。
     *
     * 以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
     *
     * 假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。
     *
     *
     *
     * 示例 1：
     *
     * 输入："RD"
     * 输出："Radiant"
     * 解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人
     * 示例 2：
     *
     * 输入："RDD"
     * 输出："Dire"
     * 解释：
     * 第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
     * 第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
     * 第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
     * 因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
     *
     *
     * 提示：
     *
     * 给定字符串的长度在 [1, 10,000] 之间.
     *
     *
     *
     * 理解题目的意思：
     *
     * 例如输入"RRDDD"，执行过程应该是什么样呢？
     *
     * 第一轮：senate[0]的R消灭senate[2]的D，senate[1]的R消灭senate[3]的D，senate[4]的D消灭senate[0]的R，此时剩下"RD"，第一轮结束！
     * 第二轮：senate[0]的R消灭senate[1]的D，第二轮结束
     * 第三轮：只有R了，R胜利
     * 估计不少同学都困惑，R和D数量相同怎么办，究竟谁赢，其实这是一个持续消灭的过程！ 即：如果同时存在R和D就继续进行下一轮消灭，轮数直到只剩下R或者D为止！
     *
     * 那么每一轮消灭的策略应该是什么呢？
     *
     *
     * @Date 2020-12-14
     * @Param [senate]
     * @return java.lang.String
     **/
    public String predictPartyVictory(String senate) {

        if(senate == null || senate.length() == 0){
            return "";
        }

        if(senate.length() <= 2){
            if(senate.charAt(0) == 'R'){
                return "Radiant";
            }else{
                return "Dire";
            }
        }

        Queue<Integer> r = new LinkedList<>();
        Queue<Integer> d = new LinkedList<>();
        for(int i = 0;i < senate.length();i++){
            if(senate.charAt(i) == 'R'){
                r.offer(i);
            }else{
                d.offer(i);
            }
        }

        //+senate.length 是为了保持相对顺序，开启下一轮操作
        while (!r.isEmpty() && !d.isEmpty()){

            int indexR = r.poll();
            int indexD = d.poll();

            if(indexR < indexD){
                r.offer(indexR + senate.length());
            }else{
                d.offer(indexD + senate.length());
            }
        }

        if(r.isEmpty()){
            return "Dire";
        }else{
            return "Radiant";
        }

    }



    /**
     * @author zlx
     * @Description 842. 将数组拆分成斐波那契序列 middle
     * 给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
     *
     * 形式上，斐波那契式序列是一个非负整数列表 F，且满足：
     *
     * 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
     * F.length >= 3；
     * 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
     * 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
     *
     * 返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
     *
     *
     *
     * 示例 1：
     *
     * 输入："123456579"
     * 输出：[123,456,579]
     * 示例 2：
     *
     * 输入: "11235813"
     * 输出: [1,1,2,3,5,8,13]
     * 示例 3：
     *
     * 输入: "112358130"
     * 输出: []
     * 解释: 这项任务无法完成。
     * 示例 4：
     *
     * 输入："0123"
     * 输出：[]
     * 解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
     * 示例 5：
     *
     * 输入: "1101111"
     * 输出: [110, 1, 111]
     * 解释: 输出 [11,0,11,11] 也同样被接受。
     *
     *
     * 提示：
     *
     * 1 <= S.length <= 200
     * 字符串 S 中只含有数字。
     *
     * 解题思路： 基于回溯+剪枝法
     *
     * @Date 2020-12-08
     * @Param [S]
     * @return java.util.List<java.lang.Integer>
     **/
    public List<Integer> splitIntoFibonacci(String S) {

        List<Integer> res = new ArrayList<>();
        backtrack(res, S, 0, 0, 0);
        return res;
    }

    public boolean backtrack(List<Integer> res, String S, int start, int sum, int prev){

        if(start == S.length()){
            return res.size() >= 3;
        }

        long curVal = 0;
        for(int i = start;i < S.length();i++){

            if(i > start && S.charAt(start) == '0'){
                break;
            }

            curVal = curVal * 10 + S.charAt(i) - '0';
            if(curVal > Integer.MAX_VALUE){
                break;
            }
            int cur = (int) curVal;
            if(res.size() >= 2){

                if(cur < sum){
                    continue;
                }else if(cur > sum){
                    break;
                }
            }

            res.add(cur);
            if(backtrack(res, S, i+1, prev + cur, cur)){
                return true;
            }else{
                res.remove(res.size() - 1);
            }
        }
        return false;
    }


    /**
     * @author zlx
     * @Description 767. 重构字符串 middle
     * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
     *
     * 若可行，输出任意可行的结果。若不可行，返回空字符串。
     *
     * 示例 1:
     *
     * 输入: S = "aab"
     * 输出: "aba"
     * 示例 2:
     *
     * 输入: S = "aaab"
     * 输出: ""
     * 注意:
     *
     * 贪心算法+最大堆顶队列
     *
     * S 只包含小写字母并且长度在[1, 500]区间内。
     * @Date 2020-11-30
     * @Param [S]
     * @return java.lang.String
     **/
    public String reorganizeString(String S) {

        if(S.length() <= 1){
            return S;
        }
        int [] sArray = new int [26];
        int maxCount = 0;
        for(char s : S.toCharArray()){
            sArray[s - 'a'] ++;
            maxCount = Math.max(maxCount, sArray[s - 'a']);
        }

        if(maxCount > (S.length() + 1) / 2){
            return "";
        }

        PriorityQueue<Character> queue = new PriorityQueue<>(new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                return sArray[o2 - 'a'] - sArray[o1 - 'a'];
            }
        });

        for(int i = 0;i < 26;i++){
            if(sArray[i] > 0){
                queue.offer((char)(i + 'a'));
            }
        }

        StringBuilder sb = new StringBuilder();
        while (queue.size() > 1){
            char c1 = queue.poll();
            char c2 = queue.poll();

            sb.append(c1);
            sb.append(c2);
            sArray[c1 - 'a'] --;
            sArray[c2 - 'a'] --;
            if(sArray[c1 - 'a'] > 0){
                queue.offer(c1);
            }

            if(sArray[c2 - 'a'] > 0){
                queue.offer(c2);
            }
        }

        if(queue.size() > 0){
            sb.append(queue.poll());
        }



        /* int start = 0, end = sArray.length - 1;
       StringBuilder sb = new StringBuilder();
        while (start < end){

            while (start < 26 && sArray[start] <= 0){
                start ++;
            }
            while (end >= 0 && sArray[end] <= 0){
                end --;
            }

            if(start < 26 && end >=0 && sArray[start] > 0 && sArray[end] > 0 && start < end){
                sArray[start] --;
                sArray[end] --;
                sb.append((char)(start + 'a'));
                sb.append((char)(end + 'a'));
            }
        }

        for(int i = 0;i < sArray.length;i++){

            if(sArray[i] >= 2){
                return "";
            }else if(sArray[i] == 1){
                sb.append((char)(i + 'a'));
            }
        }*/
        return sb.toString();
    }


    /**
     * @author zlx
     * @Description 1370. 上升下降字符串 easy
     * 给你一个字符串 s ，请你根据下面的算法重新构造字符串：
     *
     * 从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
     * 从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
     * 重复步骤 2 ，直到你没法从 s 中选择字符。
     * 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
     * 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
     * 重复步骤 5 ，直到你没法从 s 中选择字符。
     * 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
     * 在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
     *
     * 请你返回将 s 中字符重新排序后的 结果字符串 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "aaaabbbbcccc"
     * 输出："abccbaabccba"
     * 解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
     * 第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
     * 第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
     * 第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
     * 第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"
     * 示例 2：
     *
     * 输入：s = "rat"
     * 输出："art"
     * 解释：单词 "rat" 在上述算法重排序以后变成 "art"
     * 示例 3：
     *
     * 输入：s = "leetcode"
     * 输出："cdelotee"
     * 示例 4：
     *
     * 输入：s = "ggggggg"
     * 输出："ggggggg"
     * 示例 5：
     *
     * 输入：s = "spo"
     * 输出："ops"
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 500
     * s 只包含小写英文字母。
     * @Date 2020-11-25
     * @Param [s]
     * @return java.lang.String
     **/
    public String sortString(String s) {

        if(s == null || s.length() <= 1){
            return s;
        }

        int [] sArray = new int[26];
        char [] sCharArray = s.toCharArray();
        for(char tmp : sCharArray){
            sArray[tmp - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        int len = 0;
        while (len < s.length()){

            for(int i = 0;i < 26;i++){

                if(sArray[i] > 0){
                    sb.append((char)(i + 'a'));
                    sArray[i]--;
                    len++;
                }
            }

            for(int i = 25;i >=0;i--){
                if(sArray[i] > 0){
                    sb.append((char)(i +'a'));
                    sArray[i]--;
                    len++;
                }
            }
        }

        return sb.toString();

    }



    /**
     * @author zlx
     * @Description
     * @Date 2020-11-22
     * @Param [s, t]
     * @return boolean
     **/
    public boolean isAnagramI(String s, String t) {

        int [] array = new int [26];
        for(int i = 0;i < s.length();i++){
            array[s.charAt(i) - 'a'] ++;
        }

        for(int j = 0;j < t.length();j++){

            array[t.charAt(j) - 'a'] --;
        }

        for(int i : array){

            if(i != 0){
                return false;
            }
        }
        return true;
    }





    /**
     * @author zlx
     * @Description 面试题 01.05. 一次编辑 middle
     * 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
     *
     *
     *
     * 示例 1:
     *
     * 输入:
     * first = "pale"
     * second = "ple"
     * 输出: True
     *
     *
     * 示例 2:
     *
     * 输入:
     * first = "pales"
     * second = "pal"
     * 输出: False
     * @Date 2020-11-09
     * @Param [first, second]
     * @return boolean
     **/
    public boolean oneEditAway(String first, String second) {

        if((first == null && second == null) || (first.length() == 0 && first.length() == 0)){
            return true;
        }

        if(first == null && second != null || (first != null && second == null)){
            return false;
        }

        int len1 = first.length(), len2 = second.length();

        if(Math.abs(len1 - len2) >= 2){
            return false;
        }

        if(first.equals(second)){
            return true;
        }

        if(len1 < len2){
            String tmp = first;
            first = second;
            second = tmp;
        }

        if(len1 == len2){
            //替换
            int flag = 0;
            for(int i = 0;i < len1;i++) {

                if (first.charAt(i) == second.charAt(i)) {
                    continue;
                } else if(flag == 0){
                    flag = 1;
                }else {
                    return false;
                }
            }
        }else{
            //first删除一个
            int i = 0, j = 0;
            int flag = 0;
            while (i < first.length() && j < second.length()){

                if(first.charAt(i) == second.charAt(j)){
                    i++;
                    j++;
                }else if(flag == 0){
                    i++;
                    flag = 1;
                }else{
                    return false;
                }
            }

        }

        return true;
    }



    /**
     * @author zlx
     * @Description //763. 划分字母区间 middle
     * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
     *
     *
     *
     * 示例 1：
     *
     * 输入：S = "ababcbacadefegdehijhklij"
     * 输出：[9,7,8]
     * 解释：
     * 划分结果为 "ababcbaca", "defegde", "hijhklij"。
     * 每个字母最多出现在一个片段中。
     * 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
     *
     *
     * 提示：
     *
     * S的长度在[1, 500]之间。
     * S只包含小写字母 'a' 到 'z' 。
     *
     * 解题思路： 基于贪心+双指针进行求解，【每个字母只会出现在其中一个片段中】，即相同的字符在同一个字符片段中，核心是记录每个字符出现的最后一个位置
     *  然后，在利用双指针，start=0，end=0， 字符c的最后一个位置是endc， 字符片段的end >= endc, 即end = max(end, endc), 继续遍历字符，当start=end时，表示这是一个最短的字符片段，长度是end-start+1
     * @Date 2020-10-22
     * @Param [S]
     * @return java.util.List<java.lang.Integer>
     **/
    public List<Integer> partitionLabels(String S) {

        int [] array = new int [26];
        for(int i = 0;i  < S.length();i++){
            array[S.charAt(i) - 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int end = 0, start = 0;
        for(int i = 0;i < S.length();i++){
            int endTemp = array[S.charAt(i) - 'a'];
            end = Math.max(end, endTemp);
            if(i == end){
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }

    /**
     * @author zlx
     * @Description 925. 长按键入 easy
     * 你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
     *
     * 你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
     *
     *
     *
     * 示例 1：
     *
     * 输入：name = "alex", typed = "aaleex"
     * 输出：true
     * 解释：'alex' 中的 'a' 和 'e' 被长按。
     * 示例 2：
     *
     * 输入：name = "saeed", typed = "ssaaedd"
     * 输出：false
     * 解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。
     * 示例 3：
     *
     * 输入：name = "leelee", typed = "lleeelee"
     * 输出：true
     * 示例 4：
     *
     * 输入：name = "laiden", typed = "laiden"
     * 输出：true
     * 解释：长按名字中的字符并不是必要的。
     * @Date 2020-10-21
     * @Param [name, typed]
     * @return boolean
     **/
    public boolean isLongPressedName(String name, String typed) {

        List<String> nameNew = process(name);
        List<String> typedNew = process(typed);
        System.out.println("=====" + nameNew + "    " + typedNew);
        if(nameNew.size() != typedNew.size()){
            return false;
        }
        int index = 0;
        for(int i = 0;i < nameNew.size() / 2;i++){
            if(!nameNew.get(index).equals(typedNew.get(index)) || Integer.parseInt(nameNew.get(index + 1)) > Integer.parseInt(typedNew.get(index + 1))){
                return false;
            }
            index += 2;
        }

        return true;

    }

    public List<String> process(String name){

        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int start = 0, count = 1;
        while (start < name.length()){

            if(start + 1 < name.length() && name.charAt(start + 1) == name.charAt(start)){
                count++;
            }else{
                sb.append(name.charAt(start)).append(count);
                res.add(String.valueOf(name.charAt(start)));
                res.add(String.valueOf(count));
                count = 1;
            }
            start++;
        }
        System.out.println(count);
        return res;
    }


    /**
     * @author zlx
     * @Description 692. 前K个高频单词 middle
     * 给一非空的单词列表，返回前 k 个出现次数最多的单词。
     *
     * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
     *
     * 示例 1：
     *
     * 输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
     * 输出: ["i", "love"]
     * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
     *     注意，按字母顺序 "i" 在 "love" 之前。
     *
     *
     * 示例 2：
     *
     * 输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
     * 输出: ["the", "is", "sunny", "day"]
     * 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
     *     出现次数依次为 4, 3, 2 和 1 次。
     *
     *
     * 注意：
     *
     * 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
     * 输入的单词均由小写字母组成。
     *
     * 解题思路： 先统计单词出现的频率，然后再根据单词出现频率排序，如果不同的单词有相同出现频率，按字母顺序排序；
     * @Date 2020-09-30
     * @Param [words, k]
     * @return java.util.List<java.lang.String>
     **/
    public List<String> topKFrequent(String[] words, int k) {

        if(words == null || words.length <= 0 || k <= 0){
            return new ArrayList<>();
        }

        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for(String word : words){
            map.putIfAbsent(word, 0);
            map.put(word, map.get(word)+1);
        }

        List<Map.Entry<String,Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

                if(o1.getValue() == o2.getValue()){
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        for(int i = list.size()-1;i >= (list.size() - k);i--){
            res.add(list.get(i).getKey());
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 1405. 最长快乐字符串  middle
     * 如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
     *
     * 给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
     *
     * s 是一个尽可能长的快乐字符串。
     * s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
     * s 中只含有 'a'、'b' 、'c' 三种字母。
     * 如果不存在这样的字符串 s ，请返回一个空字符串 ""。
     *
     * 解题思路： 根据数量进行升序排列，循环取值，先需要判断字符串中最后2个字符是否和数量最多的字符相等，若相等，则取排序第二多的字符;不等，从数量最多进行取值
     *
     * 示例 1：
     *
     * 输入：a = 1, b = 1, c = 7
     * 输出："ccaccbcc"
     * 解释："ccbccacc" 也是一种正确答案。
     * 示例 2：
     *
     * 输入：a = 2, b = 2, c = 1
     * 输出："aabbc"
     * 示例 3：åååå
     *
     * 输入：a = 7, b = 1, c = 0
     * 输出："aabaa"
     * 解释：这是该测试用例的唯一正确答案。
     *
     *
     * 提示：
     *
     * 0 <= a, b, c <= 10
     * a + b + c > 0
     * @Date 2020-09-22
     * @Param [a, b, c]
     * @return java.lang.String
     **/
    public String longestDiverseString(int a, int b, int c) {

        MyChar [] myChars = {new MyChar('a', a), new MyChar('b', b), new MyChar('c', c)};

        StringBuilder sb = new StringBuilder();

        while(true){

            Arrays.sort(myChars);
            if(sb.length() >= 2 && sb.charAt(sb.length() - 1) == myChars[2].myChar
            && sb.charAt(sb.length() - 2) == myChars[2].myChar){
                if(myChars[1].count -- > 0){
                    sb.append(myChars[1].myChar);
                }else{
                    break;
                }
            }else {
                if(myChars[2].count -- > 0){
                    sb.append(myChars[2].myChar);
                }else{
                    break;
                }
            }
        }
        return sb.toString();
    }


    class MyChar implements Comparable{

        char myChar;
        int count;

        public MyChar(char myChar, int count) {
            this.myChar = myChar;
            this.count = count;
        }

        @Override
        public int compareTo(Object o) {
            MyChar myChar = (MyChar) o;
            return this.count - myChar.count;
        }
    }


    /**
     * @author zlx
     * @Description 459. 重复的子字符串 easy
     * 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
     *
     * 示例 1:
     *
     * 输入: "abab"
     *
     * 输出: True
     *
     * 解释: 可由子字符串 "ab" 重复两次构成。
     * 示例 2:
     *
     * 输入: "aba"
     *
     * 输出: False
     * 示例 3:
     *
     * 输入: "abcabcabcabc"
     *
     * 输出: True
     *
     * 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
     * @Date 2020-08-24
     * @Param [s]
     * @return boolean
     **/
    public boolean repeatedSubstringPattern(String s) {

        int n = s.length();
        for(int i = 1;i <= n / 2;i++){
            boolean isRepeated = true;
            if(n % i == 0){
                for(int j = i;j < n;j++){
                    if(s.charAt(j) != s.charAt(j-i)){
                        isRepeated = false;
                        break;
                    }
                }
                if(isRepeated){
                    return true;
                }
            }
        }
        return false;

    }


    public boolean is(String s){
        if(s == null || s.length() <= 0){
            return true;
        }
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < s.length()){
            Character a = s.charAt(i);
            if(a == '(' || a == '[' || a == '{'){
                stack.push(a);
            }else {
                if(!stack.isEmpty()) {
                    Character b = stack.pop();
                    if ((a == ')' && b != '(') || (a == ']' && b != '[') || (a == '}' && b != '{')) {
                        return false;
                    }
                }else{
                    return false;
                }
            }
            i++;
        }
        return stack.isEmpty();
    }


    public String addStrings(String num1, String num2) {

        if(num1 == null && num2 == null){
            return null;
        }

        if(num1 == null && num2 != null){
            return num2;
        }

        if(num1 != null && num2 == null){
            return num1;
        }

        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int flag = 0;
        StringBuilder sb= new StringBuilder();
        while (i >= 0 || j >= 0){

            int a = 0, b = 0;
            if(i >= 0){
                a = num1.charAt(i) - '0';
                i--;
            }

            if(j >= 0){
                b = num2.charAt(j) - '0';
                j --;
            }
            sb.append((a + b + flag) % 10);
            flag = (a + b + flag) / 10;
        }
        if(flag == 1){
            sb.append(flag);
        }

        return sb.reverse().toString();

    }

    /**
     * @author zlx
     * @Description 97. 交错字符串 hard
     *
     *
     * 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
     *
     * 示例 1:
     *
     * 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
     * 输出: true
     * 示例 2:
     *
     * 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
     * 输出: false
     *
     * 解题思路： 基于动态规划进行求解，创建一个dp[len1+1][len2+1]的数组
     * dp[i][j] = 1 表示s1的第1到i个字符可以组成s3前（i+j）字符串；
     * 条件： s1.chartAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j] == 1  || s2.charAt(j-1) == s3.charAt(i+j-1)) && dp[i][j-1] == 1;
     *
     *
     * dp[i][j] = 0 无法组成；
     *
     * @Date 2020-07-18
     * @Param [s1, s2, s3]
     * @return boolean
     **/
    public boolean isInterleave2(String s1, String s2, String s3) {

        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if((len1 + len2) != len3){
            return false;
        }


        int [][] dp = new int[len1 + 1][len2 + 1];
        dp[0][0] = 1;
        for(int i = 1;i <= len1;i++){

            if(s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i-1][0] == 1) {
                dp[i][0] = 1;
            }
        }


        for(int j = 1;j <= len2;j++){
            if(s2.charAt(j-1) == s3.charAt(j - 1) && dp[0][j - 1] == 1){
                dp[0][j] = 1;
            }
        }


        for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){

                if((s1.charAt(i-1) == s3.charAt(i + j - 1) && dp[i - 1][j] == 1) ||
                        (s2.charAt(j - 1) == s3.charAt(i+j - 1) && dp[i][j - 1] == 1)){

                    dp[i][j] = 1;
                }

            }
        }
        return dp[len1][len2] == 1 ? true : false;

    }


    /**
     * 67. 二进制求和 easy
     * 给你两个二进制字符串，返回它们的和（用二进制表示）。
     *
     * 输入为 非空 字符串且只包含数字 1 和 0。
     *
     *
     *
     * 示例 1:
     *
     * 输入: a = "11", b = "1"
     * 输出: "100"
     * 示例 2:
     *
     * 输入: a = "1010", b = "1011"
     * 输出: "10101"
     *
     *
     * 提示：
     *
     * 每个字符串仅由字符 '0' 或 '1' 组成。
     * 1 <= a.length, b.length <= 10^4
     * 字符串如果不是 "0" ，就都不含前导零。
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {

        int flag = 0;
        int startA = a.length() - 1;
        int startB = b.length() - 1;

        StringBuilder sb = new StringBuilder();
        while (startA >= 0 || startB >= 0){

            int valA = 0;
            int valB = 0;
            if(startA >= 0){
                valA = a.charAt(startA) - '0';
                startA --;
            }

            if(startB >= 0){
                valB = b.charAt(startB) - '0';
                startB --;
            }

            int tmpVal = valA + valB + flag;
            if(tmpVal >= 2){
                flag = 1;
                tmpVal = tmpVal % 2;
            }else{
                flag = 0;
            }
            sb.append(tmpVal);
        }

        if(flag != 0){
            sb.append(flag);
        }

        return sb.reverse().toString();
    }


    /**
     * 125. 验证回文串 easy
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     *
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     *
     * 示例 1:
     *
     * 输入: "A man, a plan, a canal: Panama"
     * 输出: true
     * 示例 2:
     *
     * 输入: "race a car"
     * 输出: false
     *
     * 输入: "  "
     * 输出: true
     *
     *
     * 输入: "."
     * 输出: true
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {

        if(s == null || s.trim().length() <= 0){
            return true;
        }

        int start = 0, end = s.length() - 1;
        while (start <= end){

            while (start < s.length() && !judeIsIllegal(s, start)){
                start ++;
            }
            while (end >= 0 && !judeIsIllegal(s, end)){
                end --;
            }
            if(start < s.length() &&  end >= 0  && s.charAt(start) != s.charAt(end) &&
                    !String.valueOf(s.charAt(start)).equalsIgnoreCase(String.valueOf(s.charAt(end)))){
                return false;
            }
            start ++;
            end --;
        }

        return true;
    }

    public  boolean judeIsIllegal(String s, int index){

        //y有一个函数方法： Character.isLetterOrDigit(char c)
        char tmp = s.charAt(index);
        if((tmp >= '0' && tmp <= '9') || (tmp >= 'a' && tmp <= 'z') || (tmp >= 'A' && tmp <= 'Z')){
            return true;
        }
        return false;
    }

    /**
     * 14. 最长公共前缀
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * 示例 1:
     *
     * 输入: ["flower","flow","flight"]
     * 输出: "fl"
     * 示例 2:
     *
     * 输入: ["dog","racecar","car"]
     * 输出: ""
     * 解释: 输入不存在公共前缀。
     * 说明:
     *
     * 所有输入只包含小写字母 a-z 。
     * @param strs
     * 解题思路： 纵向比较
     * @return
     */
    public String longestCommonPrefix(String[] strs) {

        if(strs == null || strs.length <= 0){
            return "";
        }
        String first = strs[0];
        int len = first.length();
        int count = strs.length;
        for(int i = 0;i < first.length();i++){

            char a = first.charAt(i);
            for(int j = 1;j < count;j++){
                if(strs[j].length() == i || strs[j].charAt(i) != a){
                    return first.substring(0, i);
                }
            }
        }
        return strs[0];
    }


    /**
     * @author zlx
     * @desc 3. 无重复字符的最长子串   medium
        给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

        示例 1:

        输入: "abcabcbb"
        输出: 3
        解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
        示例 2:

        输入: "bbbbb"
        输出: 1
        解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
        示例 3:

        输入: "pwwkew"
        输出: 3
        解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * @date  2020-05-25
     * @param s
     * @return int
     **/
    public int lengthOfLongestSubstring(String s) {

        if(s == null || s.length() <= 0){
            return 0;
        }

        char[] charArray = s.toCharArray();
        int maxLen = 0;
        Map<Character, Integer> map = new HashMap<>();
        List<Integer> res = new LinkedList<>();

        for(int i = 0;i < charArray.length;i++){

            if(map.containsKey(charArray[i])){
                int index = map.get(charArray[i]);
                maxLen = res.size() > maxLen ? res.size() : maxLen;
                //重复时，在list中删除从index到重复位置的数据
                for(int j = res.get(0);j <= index;j++){
                    res.remove(0);
                }

            }
            res.add(i);
            map.put(charArray[i], i);
        }

        return res.size() > maxLen ? res.size() : maxLen;

    }

    //双指针法求解
    public int lengthOfLongestSubstringII(String s) {

        if(s == null || s.length() <= 0){
            return 0;
        }

        int maxLength = 0, end = 0, n = s.length();
        HashSet<Character> hashSet = new HashSet<>();

        for(int i = 0;i < n;i++){

            if(i >= 1){
                hashSet.remove(s.charAt(i-1));
            }

            while (end < n && !hashSet.contains(s.charAt(end))){

                hashSet.add(s.charAt(end));
                end++;
            }

            maxLength = Math.max(maxLength, end - i);
        }
        return maxLength;
    }


    /**
     * @author zlx
     * @desc medium
     * 5. 最长回文子串
     * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     *
     * 示例 1：
     *
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     * 示例 2：
     *
     * 输入: "cbbd"
     * 输出: "bb"
     * @date  2020-05-25
     * @param
     * @return java.lang.String
     *
     *
     * 解题思路： 基于动态规划求解， dp[i][j]= true表示 i到j是回文
     * 当j-i <=2 s.charAt(i) == s.charAt(j)
     * 当j-i >= 3, i到j是回文的前提是： dp[i+1][j-1]是回文
     *
     **/
    public String longestPalindrome5(String s) {

        if(s == null || s.length() < 2){
            return s;
        }

        int len = s.length();
        boolean [][] dp = new boolean[len][len];
        int start = 0;
        int maxLen = 1;

        char[] charArray = s.toCharArray();
        for(int i =0 ;i < len;i++){
            dp[i][i] = true;
        }

        for(int i = 1;i < len;i++){

            for(int j = 0;j < i;j++){

                if(charArray[i] != charArray[j]){
                    dp[j][i] = false;
                }else{

                    if(i - j < 3){
                        dp[j][i] = true;
                    }else{
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                }
                if(dp[j][i] && i - j + 1 > maxLen){
                    start = j;
                    maxLen = i - j + 1;
                }
            }
        }
        return s.substring(start, start + maxLen);

    }


    /**
     * medium
     * @desc 8. 字符串转换整数 (atoi)
     * 请你来实现一个 atoi 函数，使其能将字符串转换成整数。
     *
     * 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
     *
     * 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
     * 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
     * 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
     * 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
     *
     * 在任何情况下，若函数不能进行有效的转换时，请返回 0 。
     *
     * 提示：
     *
     * 本题中的空白字符只包括空格字符 ' ' 。
     * 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
     *
     *
     * 示例 1:
     *
     * 输入: "42"
     * 输出: 42
     * 示例 2:
     *
     * 输入: "   -42"
     * 输出: -42
     * 解释: 第一个非空白字符为 '-', 它是一个负号。
     *      我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
     * 示例 3:
     *
     * 输入: "4193 with words"
     * 输出: 4193
     * 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
     * 示例 4:
     *
     * 输入: "words and 987"
     * 输出: 0
     * 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     *      因此无法执行有效的转换。
     * 示例 5:
     *
     * 输入: "-91283472332"
     * 输出: -2147483648
     * 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
     *      因此返回 INT_MIN (−231) 。
     **/
    public int myAtoiII(String str) {

        if(str == null || str.length() == 0){
            return 0;
        }
        int flag = 1;
        int res = 0;
        int i = 0;
        while (i < str.length() && str.charAt(i) == ' '){
            i++;
        }
        if(i == str.length()){
            return 0;
        }
        char firstNotEmptyChar = str.charAt(i);
        if(firstNotEmptyChar == '-') {
            flag = -1;
        }
        if(firstNotEmptyChar == '-' || firstNotEmptyChar == '+'){
            i++;
        }
        while (i < str.length() && Character.isDigit(str.charAt(i))){
            int tmp = str.charAt(i) - '0';
            if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && tmp > 7)){
                return flag > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res * 10 + tmp;
            i++;
        }
        return flag > 0 ? res : -res;
    }


    /**
     *
     * 394. 字符串解码
     * medium
     * 给定一个经过编码的字符串，返回它解码后的字符串。
     *
     * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
     *
     * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
     *
     * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
     *
     * 示例:
     *
     * s = "3[a]2[bc]", 返回 "aaabcbc".
     * s = "3[a2[c]]", 返回 "accaccacc".
     * s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
     * @param s
     * @return
     */
    public static String decodeString(String s) {

        if(s == null || s.length() == 0){
            return null;
        }
        return decodeStringWithStack(s.toCharArray());

    }

    /**
     * 基于2个栈求解
     * @param chars
     * @return
     */
    public static String decodeStringWithStack(char [] chars){

        Stack<String> resStack = new Stack<>();
        Stack<Integer> countStack = new Stack<>();
        String res = "";
        int i = 0;
        while (i < chars.length){
            if(Character.isDigit(chars[i])){
                int count = 0;
                while (Character.isDigit(chars[i])){
                    count = count * 10 + (chars[i] - '0');
                    i ++;
                }
                countStack.push(count);
            }else if(chars[i] == '['){
                resStack.push(res);
                res = "";
                i++;

            }else if(chars[i] == ']'){
                StringBuilder sb= new StringBuilder(resStack.pop());
                int repeatTimes = countStack.pop();
                for(int j = 0;j < repeatTimes;j++){
                    sb.append(res);
                }
                res = sb.toString();
                i++;
            }else{
                res += chars[i];
                i++;
            }
        }
        return res;
    }



    /*public static String res = "";
    //3[a2[c]
    public  static void dfsDecode(char [] chars, int index, String str, int count){
        if(index >= chars.length){
            if(!str.isEmpty()){
                res += str;
            }
            return ;
        }
        char tmpChar = chars[index];
        if(tmpChar >= '1' && tmpChar <= '9'){
            count = tmpChar - 48;
        }else if(tmpChar >= 'a' && tmpChar <= 'z'){
            str += tmpChar;
        }else if(tmpChar == '['){
            System.out.println("start===============");
            str = "";
        }else if(tmpChar == ']'){
            for(int i = 0; i< count;i++){
                res += str;
            }
        }
        dfsDecode(chars, index+1, str, count);

    }*/




    /**
     *  easy
     * 409. 最长回文串
     * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
     *
     * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
     *
     * 注意:
     * 假设字符串的长度不会超过 1010。
     *
     * 示例 1:
     *
     * 输入:
     * "abccccdd"
     *
     * 输出:
     * 7
     *
     * 解释:
     * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
     *
     *
     * 解题思路
     * 做过前天那题的同学，很容易想到做一个int[26+26]数组来保存各字母的个数，但A～Z和a～z在ASCII表上是分开的喔，所以存数组的时候也要分开存哦
     * 如果某字母有偶数个，因为偶数有对称性，可以把它全部用来构造回文串；但如果是奇数个的话，并不是完全不可以用来构建，也不是只能选最长的那个，而是只要砍掉1个，剩下的变成偶数就可以全部计入了
     * 但奇数字母里，可以保留1个不砍，把它作为回文串的中心，所以最后还要再加回一个1
     * 但是！如果压根没有奇数的情况，这个1也不能随便加，所以还要分情况讨论
     * @param s
     * @return
     */
    public static int longestPalindrome(String s) {

        if(s == null || s.length() == 0){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        for(char tmpChar : s.toCharArray()){
            if(map.containsKey(tmpChar)){
                map.put(tmpChar, map.get(tmpChar) + 1);
            }else{
                map.put(tmpChar, 1);
            }
            //System.out.println(tmpChar + "\n" + map);
        }
        int len = 0;
        int oddMaxLen = 0;
        int oddCount = 0;
        for(Map.Entry<Character, Integer> entry : map.entrySet()){

            if(entry.getValue() % 2 != 0){
                //oddMaxLen = entry.getValue() > oddMaxLen ? entry.getValue() : oddMaxLen;
                oddCount ++;
            }
        }
        System.out.println(map);
        System.out.println("len-----" + len + "奇数：====" + oddCount);
        System.out.println("oddMaxLen-------" + oddMaxLen);


        return oddCount == 0 ? s.length() : (s.length() - oddCount + 1);


        /*return len + oddMaxLen;*/

    }

    /**
     *
     * easy
     * 1160. 拼写单词
     * 给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。
     *
     * 假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。
     *
     * 注意：每次拼写时，chars 中的每个字母都只能用一次。
     *
     * 返回词汇表 words 中你掌握的所有单词的 长度之和。
     *
     *
     *
     * 示例 1：
     *
     * 输入：words = ["cat","bt","hat","tree"], chars = "atach"
     * 输出：6
     * 解释：
     * 可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。
     * 示例 2：
     *
     * 输入：words = ["hello","world","leetcode"], chars = "welldonehoneyr"
     * 输出：10
     * 解释：
     * 可以形成字符串 "hello" 和 "world"，所以答案是 5 + 5 = 10。
     * @param words
     * @param chars
     * @return
     */
    public static int countCharacters(String[] words, String chars) {

        if(words == null || words.length == 0 || chars == null || chars.length() == 0){
            return 0;
        }
        int len = 0;
        Map<Character, Integer> charsMap = getCharacterMap(chars);
        Map<Character, Integer> wordMap = new HashMap<>();
        boolean flag;
        for(String word : words){
            flag = true;
            wordMap = getCharacterMap(word);
            for(Map.Entry<Character, Integer> entry : wordMap.entrySet()){
                if(charsMap.containsKey(entry.getKey()) && charsMap.get(entry.getKey()) >= entry.getValue()){
                    continue;
                }else{
                    flag = false;
                    break;
                }
            }
            if(flag){
                len += word.length();
            }
        }
        return len;
    }

    public static Map<Character, Integer> getCharacterMap(String chars){
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0;i < chars.length();i++){
            Integer tmp = map.get(chars.charAt(i));
            if(tmp ==null){
                map.put(chars.charAt(i), 1);
            }else{
                map.put(chars.charAt(i), tmp+1);
            }
        }
        return map;
    }




    /*public String dfsCharArray(char [] charArray, int index, String str, int times){

        char tmp = charArray[index];
        if(tmp == '['){
            dfsCharArray(charArray, index+1, str, times);
        }else if(tmp == ']'){
            for(int i = 0;i < times;i++){

            }
            return str;
        }else if(tmp >= 'a' && tmp <= 'z'){
            str += tmp;
        }else{
           times = tmp;

        }
        return "";
    }*/


    /**
     *
     * 面试题 01.06. 字符串压缩
     * 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
     *
     * 示例1:
     *
     *  输入："aabcccccaaa"
     *  输出："a2b1c5a3"
     * 示例2:
     *
     *  输入："abbccd"
     *  输出："abbccd"
     *  解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
     * @param S
     * @return
     */
    public static String compressString(String S) {

        if(S == null || S.length() == 0){
            return S;
        }
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> map = new LinkedHashMap<>();
        map.put(S.charAt(0), 1);
        for(int i =1; i < S.length();i++){
            Character c = S.charAt(i);
            if(map.containsKey(S.charAt(i))){
                map.put(c, map.get(c) + 1);
            }else{
                sb.append(S.charAt(i-1)).append(map.get(S.charAt(i-1)));
                map.clear();
                map.put(S.charAt(i), 1);
            }
        }
        if(!map.isEmpty()){
            sb.append(S.charAt(S.length() - 1)).append(map.get(S.charAt(S.length() - 1)));
        }

        if(sb.toString().length() > S.length()){

            return S;
        }else{
            return sb.toString();
        }

    }

    /**
     * easy
     * 1071. 字符串的最大公因子
     * 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
     *
     * 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
     *
     *
     *
     * 示例 1：
     *
     * 输入：str1 = "ABCABC", str2 = "ABC"
     * 输出："ABC"
     * 示例 2：
     *
     * 输入：str1 = "ABABAB", str2 = "ABAB"
     * 输出："AB"
     * 示例 3：
     *
     * 输入：str1 = "LEET", str2 = "CODE"
     * 输出：""
     *
     *
     * 提示：
     *
     * 1 <= str1.length <= 1000
     * 1 <= str2.length <= 1000
     * str1[i] 和 str2[i] 为大写英文字母
     *
     *
     * 解题思路： 利用枚举法
     * @param str1
     * @param str2
     * @return
     */
    public static String gcdOfStrings(String str1, String str2) {

        if(str1 == null || str2 == null){
            return "";
        }

        int len1 = str1.length();
        int len2 = str2.length();
        int maxLen = len1 >= len2 ? len2 : len1;
        for(int i = maxLen; i >= 1;i--){

            if(len1 % i == 0 && len2 % i == 0){

                String temp = str1.substring(0, i);
                if(checkGcdOfStr(str1, temp) && checkGcdOfStr(str2, temp)){
                    return temp;
                }
            }
        }
        return "";
    }


    public static boolean checkGcdOfStr(String waitStr, String match){

        int n = waitStr.length() / match.length();
        String str = "";
        for(int i = 1;i <= n;i++){
            str += match;
        }
        return waitStr.equals(str);
    }




    public static void testChar(String s){

        int end = 0;
        while(end < s.length()){

            System.out.println(s.charAt(end++));
        }
    }

    /**
     *
     * 438. 找到字符串中所有字母异位词
     * 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
     *
     * 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
     *
     * 说明：
     *
     * 字母异位词指字母相同，但排列不同的字符串。
     * 不考虑答案输出的顺序。
     * 示例 1:
     *
     * 输入:
     * s: "cbaebabacd" p: "abc"
     *
     * 输出:
     * [0, 6]
     *
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
     *  示例 2:
     *
     * 输入:
     * s: "abab" p: "ab"
     *
     * 输出:
     * [0, 1, 2]
     *
     * 解释:
     * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
     * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
     * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
     *
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {

        List<Integer> res = new ArrayList<>();

        if(p == null || s == null || s.length() < p.length()){
            return res;
        }

        int [] tmp = new int[26];
        for(int i = 0;i < p.length();i++){
            tmp[p.charAt(i) - 'a'] ++;
        }

        int start = 0, end = 0;
        int count = p.length();
        while(end < s.length()){
            if(end - start == p.length() && tmp[s.charAt(start++) - 'a'] ++ >= 0){
                count ++;
            }

            if(-- tmp[s.charAt(end ++) - 'a'] >= 0){
                count --;
            }

            if(count == 0){
                res.add(start);
            }
        }
        return res;
    }


    /**
     *
     * 242. 有效的字母异位词
     *
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     *
     * 示例 1:
     *
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     *
     * 输入: s = "rat", t = "car"
     * 输出: false
     * 说明:
     * 你可以假设字符串只包含小写字母。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/valid-anagram
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param s
     * @param t
     * @return
     */
    public static boolean isAnagram(String s, String t) {

        if(s.length() != t.length()){
            return false;
        }
        int [] tmp = new int[26];
        for(int i = 0; i < s.length();i++){
            tmp[s.charAt(i) - 'a'] ++;
            tmp[t.charAt(i) - 'a'] --;
        }

        for(int i = 0;i < tmp.length;i++){
            if(tmp[i] != 0)
                return false;
        }
        return true;
    }


    /**
     *
     * 567. 字符串的排列
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
     *
     * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
     *
     * 示例1:
     *
     * 输入: s1 = "ab" s2 = "eidbaooo"
     * 输出: True
     * 解释: s2 包含 s1 的排列之一 ("ba").
     *  
     *
     * 示例2:
     *
     * 输入: s1= "ab" s2 = "eidboaoo"
     * 输出: False
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/permutation-in-string
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion(String s1, String s2) {

        int len1 = s1.length();
        int len2 = s2.length();
        if(len1 > len2){
            return false;
        }

        int [] tmp = new int [26];
        for(int i =0;i < len1;i++){

            tmp[s1.charAt(i) - 'a'] ++;
            tmp[s2.charAt(i) - 'a'] --;
        }
        if(isZero(tmp)){
            return true;
        }

        for(int i = len1;i < len2;i++){

            tmp[s2.charAt(i) - 'a'] --;
            tmp[s2.charAt(i - len1) - 'a'] ++;
            if(isZero(tmp)){
                return true;
            }
        }
        return false;

    }

    public static boolean isZero(int [] param){

        for(int i = 0;i < param.length;i++){

            if(param[i] != 0){
                return false;
            }
        }
        return true;
    }

    /**
     *
     * @param S
     * @return
     */
    public static String maskPII(String S) {

        if(S == null || S.length() == 0){
            return S;
        }

        String res = "";
        String regex = "^\\w(\\w)+@\\w(\\w)+\\.\\w((\\w)+$)";
        //regex = "^\\w";
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(S);
        if(matcher.find()){

            System.out.println("email-=-----");
            String a = S.substring(0, S.indexOf('@'));
            String b = S.substring(S.indexOf('@') + 1, S.indexOf('.'));
            String c = S.substring(S.indexOf('.') + 1);

            //System.out.println("a is: ===" + a);
            //System.out.println("b is: ===" + b);
            //System.out.println("c is: ===" + c);

            StringBuilder sb = new StringBuilder();
            sb.append(a.charAt(0)).append("*****").append(a.substring(a.length()- 1)).append(S.substring(a.length()));

            S = sb.toString().toLowerCase();

        }else{

            S = S.replaceAll("\\(", "");
            S = S.replaceAll("\\)", "");
            S = S.replaceAll("\\s+", "");
            S = S.replaceAll("\\+", "");
            S = S.replaceAll("-", "");

            int len = S.length();
            StringBuilder sb = new StringBuilder();
            if(len == 13){

                sb.append("+***-");
            }else if(len == 12){
                sb.append("+**-");
            }else if(len == 11)
                sb.append("+*-");
            sb.append("***").append("-***").append("-").append(S.substring(S.length() - 4));
            //System.out.println("phone number------" + sb.toString());
            S = sb.toString();
        }

        return S;

    }

    /**
     * 120. 三角形最小路径和
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     *
     * 例如，给定三角形：
     *
     * [
     *      [2],
     *     [3,4],
     *    [6,5,7],
     *   [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/triangle
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param triangle
     * @return
     */
    public static int minimumTotal(List<List<Integer>> triangle) {

        if(triangle == null || triangle.size() == 0){
            return 0;
        }
        int res = 0;
        List<List<Integer>> result = new ArrayList<>();
        result.add(triangle.get(0));
        for(int i = 1;i < triangle.size();i++){
            List<Integer> row = triangle.get(i);
            List<Integer> tmp = new ArrayList<>();
            for(int j = 0;j < row.size();j++){
                int tmpLeft = Integer.MAX_VALUE, tmpRight = Integer.MAX_VALUE;
                List<Integer> last = result.get(i-1);
                if(j == 0){
                    tmp.add(last.get(j) + row.get(j));
                    continue;
                }
                if(j == row.size() - 1){
                    tmp.add(last.get(j-1) + row.get(j));
                    continue;
                }
                if(j < last.size()){
                    tmpLeft = row.get(j) + last.get(j);
                }
                if(j -1 < last.size()){
                    tmpRight = row.get(j) + last.get(j-1);
                }
                tmp.add(Math.min(tmpLeft, tmpRight));
            }
            result.add(tmp);
        }
        System.out.println("-=------");
        for(List<Integer> a : result){
            System.out.println(a.toString());
        }
        List<Integer> real = result.get(triangle.size() - 1);
        Collections.sort(real);
        return real.get(0);
    }


    /**
     * 301. Remove Invalid Parentheses
     *
     * Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
     *
     * Note: The input string may contain letters other than the parentheses ( and ).
     *
     * Example 1:
     *
     * Input: "()())()"
     * Output: ["()()()", "(())()"]
     * Example 2:
     *
     * Input: "(a)())()"
     * Output: ["(a)()()", "(a())()"]
     * Example 3:
     *
     * Input: ")("
     * Output: [""]
     *
     *
     * 解题思路：
     *
     * Key Points:
     *
     * Generate unique answer once and only once, do not rely on Set.
     * Do not need preprocess.
     * Runtime 3 ms.
     * Explanation:
     * We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter.
     * The counter will increase when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(‘ in the prefix.
     *
     * To make the prefix valid, we need to remove a ‘)’. The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s.
     *
     * After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ‘)’ in two steps only with a different order.
     * For this, we keep tracking the last removal position and only remove ‘)’ after that.
     *
     * Now one may ask. What about ‘(‘? What if s = ‘(()(()’ in which we need remove ‘(‘?
     * The answer is: do the same from right to left.
     * However a cleverer idea is: reverse the string and reuse the code!
     * Here is the final implement in Java.
     * @param s
     * @return
     */
    public static List<String> removeInvalidParentheses(String s) {


        List<String> res = new ArrayList<>();

        remove(s, res, 0, 0, new char[] {'(', ')'});
        return res;
    }

    public static void remove(String s, List<String> res, int last_i, int last_j, char[] par){

        for(int stack = 0, i = last_i;i < s.length();i++){
            if(s.charAt(i) == par[0]){
                stack ++;
            }

            if(s.charAt(i) == par[1]){
                stack --;
            }

            if(stack >= 0){
                continue;
            }
            for(int j = last_j; j <= i;j++){

                if(s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1])){

                    remove(s.substring(0, j) + s.substring(j+1), res, i, j, par);
                }

            }
            return;
        }

        String reversed = new StringBuilder(s).reverse().toString();
        if(par[0] == '('){
            remove(reversed, res, 0, 0, new char[]{')', '('});
        }else {
            res.add(reversed);
        }
    }

    public static boolean isValid2(String s) {


        if(s == null || s.length() <= 0){
            return true;
        }

        Map<Character, Integer> map = new HashMap<>();
        map.put('(', 1);
        map.put(')', -1);
        map.put('[', 2);
        map.put(']', -2);
        map.put('{', 3);
        map.put('}', -3);

        Stack<Integer> stack = new Stack<>();

        for(int i = 0;i < s.length();i++){

            int temp = map.get(s.charAt(i));
            if(stack.isEmpty() || temp > 0){
                stack.push(map.get(s.charAt(i)));
            }
            else if(map.get(s.charAt(i)) + stack.peek() == 0){
                stack.pop();
            }else
                return false;
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;

    }

    /**
     *32. 最长有效括号
     *
     * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
     *
     * 示例 1:
     *
     * 输入: "(()"
     * 输出: 2
     * 解释: 最长有效括号子串为 "()"
     * 示例 2:
     *
     * 输入: ")()())"
     * 输出: 4
     * 解释: 最长有效括号子串为 "()()"
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
     *
     *
     * 解题思路： 利用栈解题， 先找到所有可以匹配的索引号，然后找出最长连续数列！
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {

        if(s == null || s.length() == 0){
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int res = 0;

        stack.push(-1);
        for(int i = 0;i < s.length();i ++){

            char tmp = s.charAt(i);
            if(tmp == '('){
               stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
        return res;
    }


        /**
         * 76. 最小覆盖子串
         * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
         *
         * 示例：
         *
         * 输入: S = "ADOBECODEBANC", T = "ABC"
         * 输出: "BANC"
         * 说明：
         *
         * 如果 S 中不存这样的子串，则返回空字符串 ""。
         * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
         *
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode-cn.com/problems/minimum-window-substring
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         *
         *
         * 解题思路： 滑动窗口思想
         * @param s
         * @param t
         * @return
         */
    public static String minWindow(String s, String t) {

        if(s.isEmpty() || t.isEmpty()){
            return "";
        }
        char [] s_array = s.toCharArray();

        int[] array = new int[128];
        for(char tmp : t.toCharArray()){
            array[tmp] ++;
        }
        int left  = 0, right = 0, count = t.length(), minStart = 0;
        int minLen = Integer.MAX_VALUE;
        while(right < s.length()){
            if(array[s_array[right]] > 0){
                count --;
            }
            array[s_array[right]] --;
            //t中字符都找到
            while(count == 0){

                if(right - left < minLen){
                    minLen = right - left + 1;
                    minStart = left;
                }
                array[s_array[left]] ++;
                if(array[s_array[left]] > 0){
                    count++;
                }
                left++;
            }
            right++;
        }
        if(minStart + minLen > s.length())
            return "";
        return s.substring(minStart, minStart + minLen);
    }


    //public static Boolean

    /**
     * 30. 串联所有单词的子串(substring-with-concatenation-of-all-words)
     * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
     *
     * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：
     *   s = "barfoothefoobarman",
     *   words = ["foo","bar"]
     * 输出：[0,9]
     * 解释：
     * 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
     * 输出的顺序不重要, [9,0] 也是有效答案。
     * 示例 2：
     *
     * 输入：
     *   s = "wordgoodgoodgoodbestword",
     *   words = ["word","good","best","word"]
     * 输出：[]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
     *
     *
     *
     * 思路：
     * 基于2个 map进行解题， 一个map用于存储 key是word， value是相同word的次数
     * 从0开始遍历字符串s, 每次长度是word.length, 存放在另一个map中。
     *
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> res = new ArrayList<>();

        if(s == null || s.length() == 0 || words == null || words.length == 0){
            return res;
        }

        Map<String, Integer> map = new HashMap<>();
        for(String word: words){
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        int n = s.length();
        int num = words.length;
        int len = words[0].length();

        for(int i =0; i < n - num * len + 1;i++){

            Map<String, Integer> seen = new HashMap<>();
            int j = 0;

            while(j < num){

                String word = s.substring(i + j * len, i + j* len + len);
                if(map.containsKey(word)){
                    seen.put(word, seen.getOrDefault(word, 0) + 1);
                    if(seen.get(word) > map.get(word)){
                        break;
                    }
                }else{
                    break;
                }
                j++;
            }
            if(j == num){
                res.add(i);
            }
        }

        return res;
    }

    /**
     * 49. 字母异位词分组
     * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
     *
     * 示例:
     *
     * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
     * 输出:
     * [
     *   ["ate","eat","tea"],
     *   ["nat","tan"],
     *   ["bat"]
     * ]
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {

        List<List<String>> res = new ArrayList<>();
        if(strs == null || strs.length <= 0){
            return res;
        }

        Map<String, List<String>> map = new HashMap<>();
        for(int i = 0;i < strs.length;i++){

            char[] tmp = strs[i].toCharArray();
            Arrays.sort(tmp);

            System.out.println(String.valueOf(tmp));
            if(!map.containsKey(String.valueOf(tmp))){
                map.put(String.valueOf(tmp), new ArrayList<>());
            }
            map.get(String.valueOf(tmp)).add(strs[i]);
        }
        return new ArrayList<List<String>>(map.values());


        /*boolean [] isUsed = new boolean [strs.length];
        for(int i = 0; i < strs.length;i++){
            if(isUsed[i]){
                continue;
            }
            List<String> tmp = new ArrayList<>();
            tmp.add(strs[i]);
            for(int j = i+1;j < strs.length;j++){
                if(!isUsed[j] && strs[i].length() == strs[j].length() && isContainsSameCharcther(strs[i], strs[j])){

                    isUsed[j] = true;
                    tmp.add(strs[j]);
                }
            }
            res.add(tmp);
        }
        return res;
        */
    }


    public Boolean isContainsSameCharcther(String str1, String str2){

        HashSet<Character> hashSet = new HashSet<>();
        for(int i =0;i < str1.length();i++){
            hashSet.add(str1.charAt(i));
        }
        for(int i = 0;i < str2.length();i++){
            if(!hashSet.contains(str2.charAt(i))){
                return false;
            }
        }
        return true;
    }


    /**
     * 791. Custom Sort String
     * @param S
     * @param T
     * @return
     */
    public static String customSortString(String S, String T) {

        Map<Character, Integer> mapS = new LinkedHashMap<>();
        for(int i =0;i < S.length();i++){
            mapS.put(S.charAt(i), i);
        }

        Map<Character, Integer> mapT = new LinkedHashMap<>();
        for(int i = 0;i < T.length();i++){
            if(!mapT.containsKey(T.charAt(i))){
                mapT.put(T.charAt(i), 1);
            }else{
                mapT.put(T.charAt(i), mapT.get(T.charAt(i)) + 1);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0; i< S.length();i++){
            if(mapT.containsKey(S.charAt(i))){
                for(int j =0;j < mapT.get(S.charAt(i));j++){
                    sb.append(S.charAt(i));
                }
            }
        }
        for(Map.Entry<Character, Integer> entry : mapT.entrySet()){

            if(!mapS.containsKey(entry.getKey())){
                for(int i =0;i < entry.getValue();i++){
                    sb.append(entry.getKey());
                }
            }
        }
        return sb.toString();
    }

    /**
     * 709. To Lower Case
     * @param str
     * @return
     */
    public static String toLowerCase(String str) {

        if(str == null || str.length() == 0){
            return str;
        }
        StringBuilder sb = new StringBuilder();
        for(int i =0;i < str.length();i++){

            char tmp = str.charAt(i);
            if(tmp >= 'A' && tmp <= 'Z'){
                tmp = (char)(tmp + 32);
            }
            sb.append(tmp);
        }
        return sb.toString();

    }


    /**
     * 583. Delete Operation for Two Strings
     * @param word1
     * @param word2
     * 本质问题是求最长公共字序列
     * @return
     */
    public static int minDistance(String word1, String word2) {

        if(word1 == null && word2 == null){
            return 0;
        }

        if(word1 == null && word2 != null){
            return word2.length();
        }

        if(word1 != null && word2 == null){
            return word1.length();
        }

        int [][] res = new int [word1.length() + 1][word2.length() + 1];
        for(int i = 1;i <= word1.length();i++){
            for(int j =1; j <= word2.length();j++){

                if(word1.charAt(i-1) != word2.charAt(j-1)){

                    res[i][j] = Math.max(res[i-1][j], res[i][j-1]);
                }else{
                    res[i][j] = res[i-1][j-1] + 1;
                }
            }
        }
        int maxLength = res[word1.length()][word2.length()];
        System.out.println("maxLength is :" + maxLength);
        return word1.length() - maxLength + word2.length() - maxLength;
    }


    /**
     * 443. String Compression
     */
    public static int compress(char[] chars) {
        if(chars == null || chars.length == 0){
            return 0;
        }
        if(chars.length == 1){
            return 1;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(chars[0]);
        int count = 1;
        for(int i =1;i < chars.length;i++){

            if(chars[i] == chars[i-1]){
                count++;
            }else{
                if(count != 1){
                    sb.append(String.valueOf(count));
                    count = 1;
                }
                sb.append(chars[i]);
            }
        }
        if(count != 1){
            sb.append(count);
        }
        //chars = sb.toString().toCharArray();
        String res = sb.toString();
        for(int i =0;i < res.length();i++){
            chars[i] = res.charAt(i);
        }
        System.out.println("result chars is :" + new String(chars));
        System.out.println("res is: " + sb.toString());
        return sb.toString().length();
    }

    /**
     * 58. Length of Last Word
     * @param s
     * @return
     */
    public static int lengthOfLastWord(String s) {
        if(s == null || s.length() == 0 || s == " "){
            return 0;
        }
        String [] temp = s.split("\\s");
        if(temp == null || temp.length == 0){
            return 0;
        }
        String str = temp[temp.length - 1];
        if(str.length() == 1 && str == " "){
            return 0;
        }
        return str.length();
    }


    /**
     * 434. Number of Segments in a String
     * Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
     *
     * Please note that the string does not contain any non-printable characters.
     *
     * 空格分割
     *
     */
    public static int countSegment(String s){

        if(s == null || s == "" || s.length() == 0 || s == " "){
            return 0;
        }

        int res = 0;
        for(int i =0;i < s.length();i++){
            //防止出现多个连续空格
            if(s.charAt(i) == ' '&& i != 0 && s.charAt(i-1) != ' '){
                res ++;
            }
        }
        if(s.charAt(s.length() - 1) != ' '){
            res++;
        }
        return res;
    }



    /**
     * 678. Valid Parenthesis String  (未解决)
     * "*()(())*()(()()((()(()()*)(*(())((((((((()*)(()(*)"   fasle
     */
    public static boolean checkValidString(String s) {

        if(s == null || s == "" || s.length() == 0){
            return true;
        }
        if(s.charAt(0) == ')'){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        return checkValidStringDG(s, 0, stack);

    }

    public static boolean checkValidStringDG(String s, int i, Stack<Character> stack){
        if(i >= s.length()){
            if(stack.isEmpty()){
                return true;
            }
            return false;
        }
        Character temp = s.charAt(i);
        if(temp == ')' && stack.isEmpty()){
            return false;
        }

        if(temp == '*'){

        }


        if(temp == '('){
            stack.push(temp);
            return checkValidStringDG(s, i++, stack);
        }else if(temp == ')'){
            if(!stack.isEmpty()){
                stack.pop();
                return checkValidStringDG(s, i++, stack);
            }
        }

        return false;


    }





    /**
     * 856. Score of Parentheses
     * Given a balanced parentheses string S, compute the score of the string based on the following rule:
     *
     * () has score 1
     * AB has score A + B, where A and B are balanced parentheses strings.
     * (A) has score 2 * A, where A is a balanced parentheses string.
     *
     * ()() 2
     * (()) 2
     * (()(())) 6
     *
     * 思路： 有题目中的要求知道只有()才能得分，而且嵌套的()会将得分加倍，所以题目可以简化为求所有的()的得分，其中得分多少取决于被嵌套的层数。
     * @param s
     * @return
     */
    public static int scoreOfParentheses(String s){

        if(s.length() == 2){
            return 1;
        }

        int res =0, deep = 0;
        //记录上一个字符
        char last = ' ';
        for(int i =0;i < s.length();i++){

            char temp = s.charAt(i);
            if(temp == '('){
                //深度变大
                deep++;
            }else{
                //深度减少
                deep--;
                //上一个是（，表示是一对，可以分
                if(last == '('){
                    res += 1 << deep;
                }
            }
           last = temp;
        }
        return res;
    }






    /**
     * 43. Multiply Strings
     * 解题思路： 低位分别相乘再相加
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {

        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();
        int [] res = new int[len1 + len2];

        for(int i = len1 - 1;i >= 0;i--){
            for(int j =len2 - 1; j >= 0;j--){

                int temp = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;

                int sum = temp + res[p2];
                //高位
                res[p1] += sum/10;
                //低位
                res[p2] = sum % 10;
                //System.out.println("res[" + p1 + "] =" + res[p1] + "   res[" + p2 + "]= " + res[p2]);
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int temp : res){
            sb.append(temp);
        }
        System.out.println(sb.toString());
        if(sb.toString().charAt(0) == '0'){
            return sb.toString().substring(1);
        }
        return sb.toString();
    }

    /**
     * 537. Complex Number Multiplication
     * Given two strings representing two complex numbers.
     *
     * You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
     * @param a
     * @param b
     * @return
     */
    public static String complexNumberMultiply(String a, String b) {

        String c = a.substring(0, a.indexOf('+'));
        String d = a.substring(a.indexOf('+') + 1, a.indexOf('i'));

        String e = b.substring(0, b.indexOf('+'));
        String f = b.substring(b.indexOf('+') + 1, b.indexOf('i'));

        System.out.println(c);
        System.out.println(d);
        System.out.println(e);
        System.out.println(f);


        Integer num = Integer.parseInt(c) * Integer.parseInt(e) - Integer.parseInt(d) * Integer.parseInt(f);
        Integer complex = Integer.parseInt(c) * Integer.parseInt(f) + Integer.parseInt(d) * Integer.parseInt(e);

        String res = num + "+" + complex + "i";

        System.out.println("a is: " + a  + "======b is :" + b + "  res is: " + res);
        return res;
    }

    /**
     * 7.Reverse Integer
     * Given a 32-bit signed integer, reverse digits of an integer.
     * Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
     * @param x
     * @return
     */
    public static int reverse(int x) {

        long res = 0;
        while(x != 0){

            //System.out.println(x % 10);
            res = res * 10 + x % 10;
            x = x / 10;
        }
        if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE){
            return 0;
        }
        System.out.println("res is: " + res);
        return (int)res;

    }


    /**
     *
     *
     * 暂时为解决
     *
     * 564. Find the Closest Palindrome
     * Given an integer n, find the closest integer (not including itself), which is a palindrome.
     *
     * The 'closest' is defined as absolute difference minimized between two integers.
     *
     * Example 1:
     * Input: "123"
     * Output: "121"
     *
     * @param n
     * @return
     */
    public static String nearestPalindromic(String n) {

        if(n.length() == 1 && n.equals("0")){
            return "1";
        }
        if(n.length() == 1){
            return String.valueOf(Integer.parseInt(n) - 1);
        }
        if(n.equals("10") || n.equals("11")){
            return "9";
        }
        if(n.length() == 2 && Long.parseLong(n) >= 12 && Long.parseLong(n) <= 16){
            return "11";
        }

        if(n.length() == 2 && Long.parseLong(n) >= 17 && Long.parseLong(n) <= 19){
            return "22";
        }
        int len = n.length();
        String needReverse;
        boolean isOdd = false;
        //偶数
        if(len % 2 == 0){
            needReverse = n.substring(0, len/2);
        }else{         //奇数
            needReverse = n.substring(0, len/2 + 1);
            isOdd = true;
        }
        Long [] res = new Long[3];
        long needReverseLong = Long.parseLong(needReverse);
        for(int i = -1;i <= 1;i++){
            if(needReverseLong == 1){

            }
            long tempLong = needReverseLong + i;
            String temp = String.valueOf(tempLong);
            if(isOdd && temp.length() == needReverse.length()){
                temp += new StringBuffer(temp.substring(0, temp.length() - 1)).reverse().toString();
            }else if(!isOdd && temp.length() != needReverse.length()){

                temp += new StringBuffer(temp).reverse().toString() + '9';
            }else{
                temp += new StringBuffer(temp).reverse().toString();
            }
            res[i+1] = Long.parseLong(temp);
        }

        String result = "";
        Long minDiff = Long.MAX_VALUE;
        for(int i =0;i < res.length;i++){
            long temp = Math.abs(Long.parseLong(n) - res[i]);
            System.out.println("old is: " + n + "   new is: " + res[i]);
            if(temp < minDiff && temp != 0){
                result = String.valueOf(res[i]);
                minDiff = temp;
            }
        }
        return result;
    }


    public static String nearestPalindromic1(String n) {

        if(n.length() == 1 && n.equals("0")){
            return "1";
        }
        if(n.length() == 1){
            return String.valueOf(Integer.parseInt(n) - 1);
        }
        int len = n.length();
        String needReverse;
        boolean isOdd = false;
        //偶数
        if(len % 2 == 0){
            needReverse = n.substring(0, len/2);
        }else{         //奇数
            needReverse = n.substring(0, len/2 + 1);
            isOdd = true;
        }
        if(judge(n)){
            return String.valueOf(Long.parseLong(n) - 1);
        }
        String [] res = new String[3];
        for(int i = -1;i <= 1;i++){
            boolean isShorter = false;
            String temp = needReverse;
            if(temp.charAt(needReverse.length() - 1) == '0' && i == -1){
                temp = temp.substring(0, needReverse.length() - 2) + '9';
                isShorter = true;
            }
            else if(temp.charAt(needReverse.length() - 1) == '9' && i == 1){
                temp = temp.substring(0,needReverse.length() -1) + '0';
            }else{
                temp = temp.substring(0,needReverse.length() -1) + (temp.charAt(needReverse.length() - 1) + i - 48) ;
            }
            String result = temp;
            if(isOdd && !isShorter){
                result += new StringBuffer(result.substring(0, result.length() - 1)).reverse().toString();
            }else{
                result += new StringBuffer(result).reverse().toString();
            }
            res[i+1] = result;
        }

        String result = "";
        Long minDiff = Long.MAX_VALUE;
        for(int i =0;i < res.length;i++){
            long temp = Math.abs(Long.parseLong(n) - Long.parseLong(res[i]));
            System.out.println("old is: " + n + "   new is: " + res[i]);
            if(temp < minDiff && temp != 0){
               result = res[i];
               minDiff = temp;
            }
        }
        return result;
    }

    public static boolean judge(String input){

        if(input.charAt(0) == '1'){
            for(int i = 1;i< input.length();i++){
                if(input.charAt(i) != '0'){
                    return false;
                }
            }
        }else{
            return false;
        }
        return true;
    }


    /**
     * 17. Letter Combinations of a Phone Number
     * 根据数字键盘和英文字符间的映射关系，求出不同的组合
     * Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
     *
     * A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
     *
     *
     *
     * Example:
     *
     * Input: "23"
     * Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
     * @param digits
     * @return
     */
    public static List<String> letterCombination(String digits){

        if(digits == null || digits.length() == 0){
            return new ArrayList<>();
        }
        List<String> res = new ArrayList<>();
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a', 'b','c'));
        map.put('3', Arrays.asList('d', 'e','f'));
        map.put('4', Arrays.asList('g', 'h','i'));
        map.put('5', Arrays.asList('j', 'k','l'));
        map.put('6', Arrays.asList('m', 'n','o'));
        map.put('7', Arrays.asList('p', 'q','r','s'));
        map.put('8', Arrays.asList('t','u', 'v'));
        map.put('9', Arrays.asList('w','x', 'y','z'));
        getLetterCombination(digits, 0, res, map, "");
        return res;
    }

    public static void getLetterCombination(String digitis, int start, List<String> res, Map<Character, List<Character>> map, String s){


        if(s.length() == digitis.length()){
            res.add(s);
            return;
        }

        Character character = digitis.charAt(start);
        List<Character> characterList= map.get(character);
        for(Character character1 : characterList){
            getLetterCombination(digitis, start+1, res, map, s+character1);
        }


    }

    /**
     * 20. Valid Parentheses
     * @param s
     * @return
     */
    public static boolean isValid(String s) {

        Integer [] temp = new Integer[s.length()];
        for(int i =0;i< s.length();i++){
            Character character = s.charAt(i);
            if(character == '('){
                temp[i] = 1;
            }else if(character == ')'){
                temp[i] = -1;
            }else if(character == '{'){
                temp[i] = 2;
            }else if(character == '}'){
                temp[i] = -2;
            }else if(character == '['){
                temp[i] = 3;
            }else{
                temp[i] = -3;
            }
        }
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i < temp.length;i++){
            int tmp = temp[i];
            if(stack.empty()){
                stack.push(tmp);
            }else{
                if(stack.peek() + tmp == 0){
                    stack.pop();
                }else{
                    stack.push(tmp);
                }
            }
        }
        //System.out.println(stack);
        if(stack.empty()){
            return true;
        }else{
            return false;
        }

    }


    /**
     * Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
     *
     * For example, given n = 3, a solution set is:
     *
     * [
     *   "((()))",
     *   "(()())",
     *   "(())()",
     *   "()(())",
     *   "()()()"
     * ]
     *
     * 利用递归思想解决问题
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(1, 0, n, res,"(");
        return res;
    }

    private static void helper(int left, int right, int n, List<String> res, String s){
        if(right == n){
            res.add(s);
            return ;
        }

        if(left < n){
            helper(left+1, right, n, res, s + "(");
        }

        if(right < n && right < left){
            helper(left, right+1, n, res, s + ")");
        }
    }

    /**
     * 65. Valid Number
     * @param s
     * @return
     */
    public static boolean isNumber(String s) {

        //无用
        String reg = "^[\\d|+|-]\\d*(\\.\\d+)?(e[-|+]?\\d+)?$";
        //匹配以.数字 开头的数据，如 .1, .236
        String reg2 = "^(\\.)\\d+(e[-|+]?\\d+)?$";
        //匹配以数字开头的数字 88.8e10
        String reg3 = "^[\\d]\\d*(\\.\\d*)?(e[-|+]?\\d+)?$";
        //匹配以+/-数字 开头的数字 +88.8e10
        String reg4 = "^[+|-]\\d+(\\.\\d*)?(e[-|+]?\\d+)?$";
        //匹配+/-. 开头的数字，如 +.1
        String reg5 = "^[+|-]\\.\\d+?";
        //Pattern pattern = Pattern.compile(reg);

        Pattern pattern2 = Pattern.compile(reg2);
        Pattern pattern3 = Pattern.compile(reg3);
        Pattern pattern4 = Pattern.compile(reg4);
        Pattern pattern5 = Pattern.compile(reg5);
        //Matcher matcher = pattern.matcher(s.trim());
        Matcher matcher2 = pattern2.matcher(s.trim());
        Matcher matcher3 = pattern3.matcher(s.trim());
        Matcher matcher4 = pattern4.matcher(s.trim());
        Matcher matcher5 = pattern5.matcher(s.trim());
        boolean res = matcher2.find() || matcher3.find() || matcher4.find()|| matcher5.find();
        System.out.println(s + " =>" + res);
        return res;

    }


    /**
     * 165. Compare Version Numbers
     * Compare two version numbers version1 and version2.
     * If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.
     *
     * You may assume that the version strings are non-empty and contain only digits and the . character.
     *
     * The . character does not represent a decimal point and is used to separate number sequences.
     *
     * For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
     *
     * You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.
     * @param version1
     * @param version2
     *
     * Input: version1 = "0.1", version2 = "1.1"
     * Output: -1
     * Example 2:
     *
     * Input: version1 = "1.0.1", version2 = "1"
     * Output: 1
     * Example 3:
     *
     * Input: version1 = "7.5.2.4", version2 = "7.5.3"
     * Output: -1
     * Example 4:
     *
     * Input: version1 = "1.01", version2 = "1.001"
     * Output: 0
     * Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”
     * Example 5:
     *
     * Input: version1 = "1.0", version2 = "1.0.0"
     * Output: 0
     * Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"
     * @return
     */
    public static int compareVersion(String version1, String version2) {

        String [] version1Array = version1.split("\\.");
        String [] version2Array = version2.split("\\.");
        int len1 = version1Array.length;
        int len2 = version2Array.length;
        int len = len1 <= len2 ? len1 : len2;
        for(int i =0;i < len;i++){
            int a = Integer.parseInt(version1Array[i]);
            int b = Integer.parseInt(version2Array[i]);
            if(a > b){
                return 1;
            }else if(a < b){
                return -1;
            }
        }

        if(len1 < len2){
           for(int i = len;i<len2;i++){
               int c = Integer.parseInt(version2Array[i]);
               if(c > 0){
                   return -1;
               }
           }
        }else if(len1 > len2){
            for(int i = len;i<len1;i++){
                int c = Integer.parseInt(version1Array[i]);
                if(c > 0){
                    return 1;
                }
            }
        }
        return 0;

    }

    /**
     *
     *
     * 639 decode ways II
     *  ** 96;
     *  1* 18
     * @param s
     * @return
     */
    public static int numDecodings(String s) {

        int[] dp = new int[s.length() + 1];
        System.out.println(dp.length);
        dp[0] = 1;
        char first = s.charAt(0);
        char last;
        if(first == '0'){
            return 0;
        }else if(first == '*'){
            dp[1] = 9;
        }else{
            dp[1] = 1;
        }

        for(int i = 2;i <= s.length();i++){
            first = s.charAt(i-1);
            last = s.charAt(i-2);
            if(first == '0'){
                if(last == '*'){
                    dp[i] = dp[i] + dp[i-2] + 1;
                }

                if(last <= '2' && last >= '1'){
                    dp[i] = dp[i] + dp[i-2];
                }

            }else if(first == '*'){
                dp[i] = dp[i] + dp[i-1] + 8;
                if(last == '*'){
                    dp[i] = dp[i] + dp[i-2] + 17;
                }else if(last == '1'){
                    dp[i] = dp[i] + dp[i-2] + 8;
                }else if(last == '2'){
                    dp[i] = dp[i] + dp[i-2] + 5;
                }
            }else{
                dp[i] += dp[i-1];
                if(last == '*'){
                    if(first >= '1' && first <= '6'){
                        dp[i] = dp[i] + dp[i-2] + 1;
                    }else{
                        dp[i] += dp[i-2];
                    }
                }else if(last >= '1' && last <='2'){
                    dp[i] += dp[i-2];
                }
            }
        }

        for(int i =0; i< s.length()+1;i++){
            System.out.print(dp[i] + "   ");
        }
        System.out.println();
        return dp[s.length()];

    }




    /**
     * @Date 2019/5/17
     *91. Decode Ways
     * A message containing letters from A-Z is being encoded to numbers using the following mapping:
     *
     * 'A' -> 1
     * 'B' -> 2
     * ...
     * 'Z' -> 26
     * Given a non-empty string containing only digits, determine the total number of ways to decode it.
     *
     * Example 1:
     *
     * Input: "12"
     * Output: 2
     * Explanation: It could be decoded as "AB" (1 2) or "L" (12).
     * Example 2:
     *
     * Input: "226"
     * Output: 3
     * Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
     * @param s
     * @return
     *
     * 核心 利用DP思想，dp[i]表示到i个元素有dp[i]种组合方式，
     * 当s[i] == '0' , 10<=s[i-1]s[i]<=20 dp[i]= dp[i] + dp[i-2]
     * 当s[i] != '0'时，1<=s[i]<=9, dp[i]= dp[i]+dp[i-1],  11<=s[i-1]s[i]<=26 dp[i]= dp[i] + dp[i-2]
     */
    public static int numDecoding(String s){

        if(s == null || s.length() == 0){
            return 0;
        }

        int []dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for(int i =2; i<= s.length();i++){

            int first = Integer.valueOf(s.substring(i-1, i));
            int second = Integer.valueOf(s.substring(i-2, i));
            if(s.charAt(i-1) == '0'){
                if(second >= 10 && second <= 26){
                    dp[i] += dp[i-2];
                }
            }else{
                if(first >= 1 && first <= 9){
                    dp[i] += dp[i-1];
                }
                if(second >= 11 && second <= 26){
                    dp[i] += dp[i-2];
                }
            }



        }
        return dp[s.length()];
    }


    /**
     *
     * @param s
     * @return
     */
    public static int numDecoding2(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

        for (int i = n - 2; i >= 0; i--)
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];

        return memo[0];
    }

    /**
     * 12. Integer to Roman
     * Symbol       Value
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * num 1 to 3999
     * For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
     *
     * Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
     *
     * I can be placed before V (5) and X (10) to make 4 and 9.
     * X can be placed before L (50) and C (100) to make 40 and 90.
     * C can be placed before D (500) and M (1000) to make 400 and 900.
     * Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
     *
     * Example 1:
     *
     * Input: 3
     * Output: "III"
     * Example 2:
     *
     * Input: 4
     * Output: "IV"
     * Example 3:
     *
     * Input: 9
     * Output: "IX"
     * Example 4:
     *
     * Input: 58
     * Output: "LVIII"
     * Explanation: L = 50, V = 5, III = 3.
     * Example 5:
     *
     * Input: 1994
     * Output: "MCMXCIV"
     * Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
     * @param num
     * @return
     */
    public static String intToRoman(int num) {

        int times = 0;
        StringBuilder sb = new StringBuilder();
        while(num != 0){

            if(num < 5){
                if(num == 4){
                    sb.append("IV");
                    num = num - 4;
                }else{
                    sb.append(buildString(num, "I"));
                    break;
                }
            }else if(num < 10){
                if(num == 9){
                    sb.append("IX");
                    num = num - 9;
                }else{
                    times = num/5;
                    num = num - num / 5 * 5;
                    sb.append(buildString(times, "V"));
                }
            }else if(num < 50){
                if(num >= 40){
                    sb.append("XL");
                    num = num - 40;
                }else{
                    times = num / 10;
                    num = num - times * 10;
                    sb.append(buildString(times, "X"));
                }

            }else if(num < 100){
                if(num >= 90){
                    sb.append("XC");
                    num = num - 90;
                }else{
                    times = num / 50;
                    num = num - times * 50;
                    sb.append(buildString(times, "L"));
                }
            }else if(num < 500){
                if(num >= 400){
                    sb.append("CD");
                    num = num - 400;
                }else{
                    times = num / 100;
                    num = num - times * 100;
                    sb.append(buildString(times, "C"));
                }
            }else if(num < 1000){
                if(num >= 900){
                    sb.append("CM");
                    num = num - 900;
                }else{
                    num = num - 500;
                    sb.append("D");
                }

            }else{
                times = num / 1000;
                num = num - times * 1000;
                sb.append(buildString(times, "M"));
            }

        }
        return sb.toString();
    }

    public static String buildString(int count, String flag){

        String sb = "";
        for(int i = 0;i < count;i++){
            sb += flag;
        }
        return sb;
    }

    /**
     * 优解
     * @param num
     * @return
     */
    public static String intToRoman2(int num) {
        String M[] = {"", "M", "MM", "MMM"};
        String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }

    /**
     * 8. String to Integer (atoi)
     *
     * @Date 2019/5/12
     *
     * Implement atoi which converts a string to an integer.
     *
     * The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
     *
     * The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
     *
     * If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
     *
     * If no valid conversion could be performed, a zero value is returned.
     *
     * Note:
     *
     * Only the space character ' ' is considered as whitespace character.
     * Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
     * @param str
     * @return
     */
    public static int myAtoi(String str) {

        str = str.trim();
        if(str == null || str.length() == 0 || str == ""){
            return 0;
        }
        int multi = 1;
        int res = 0;
        //长度 >= 2
        for(int i =0;i < str.length();i++){

            char tmp = str.charAt(i);
            boolean isNum = isNumericaChar(tmp);

            if(i == 0){
                if(isNum){
                    multi = 1;
                    res = res * 10 + tmp - 48;
                }else if( tmp == 43){
                    multi = 1;
                }else if(tmp == 45){
                    multi = -1;
                }else{
                    return 0;
                }
            }else{
                if(isNum){
                    if(res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && tmp - 48 > 7)) {
                        if (multi == 1) {
                            return Integer.MAX_VALUE;
                        } else if(multi == -1) {
                            return Integer.MIN_VALUE;
                        }
                    }else{
                        res = res * 10 + (tmp - 48);
                    }
                }else{
                    break;
                }
            }
        }
        res = res * multi;
        return res;

    }


    public static Boolean isNumericaChar(char ch){
        if(ch >= 48 && ch <= 57){
            return true;
        }else{
            return false;
        }
    }




    /**
     * char转int
     * @param ch
     * @return
     */
    public static int changeCharToInt(char ch){
        if(ch >= 48 && ch <= 57){
            return ch-48;
        }else if(ch == 43){    //+
            return 10;
        }else if(ch == 45){    //-
            return 11;
        }else{
            return -1;
        }
    }

    /**
     *
     * 6. ZigZag Conversion
     * The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
     *
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * And then read line by line: "PAHNAPLSIIGYIR"
     *
     * Write the code that will take a string and make this conversion given a number of rows:
     *
     * string convert(string s, int numRows);
     * Example 1:
     *
     * Input: s = "PAYPALISHIRING", numRows = 3
     * Output: "PAHNAPLSIIGYIR"
     * Example 2:
     *
     * Input: s = "PAYPALISHIRING", numRows = 4
     * Output: "PINALSIGYAHRPI"
     * Explanation:
     *
     * P     I    N
     * A   L S  I G
     * Y A   H R
     * P     I
     *
     * 以上图为例，我们将变形后的数据根据斜着的 V 形来进行分组，每一组 V 字形的长度为 size = 2 * line - 2，line 是行数，对于上图 size = 8，对于垂直向下的一列元素来说，每一组向下的列之间间隔 size 大小，即一组元素的个数，比如0和8、2和10之间都相差了 size 大小。
     * 对于斜向上的元素来说，它们的位置位于当前组 size - i（i 为该元素所在的行数，一组有 size 个字符，第 i 行就代表着倒数第 i 个元素，所以位置为 size - 1）。当前组的第一个字符所在位置为 j - i （j 为与斜向上的元素同在一行的，垂直向下的列的元素在字符串中的序号，i 为它们共同的行号）。,即：j-i 就是 zigzag 的起始字符，然后我们是要倒数第i个，因为一个 zigzag 有 size 个字符，所以倒数第 i 个就是 size-i ，我们要赋值的字符就是 (j-i)+(size-i)
     *
     * @param s
     * @param numRows
     * @return
     */
    public static String convert(String s, int numRows) {

        if(s== null || s.length() <= numRows || numRows == 1){
            return s;
        }
        int m = 2 * numRows -2;

        StringBuilder sb = new StringBuilder();
        for(int i =0;i<numRows;i++){
            for(int j = i;j < s.length();j+=m){

                sb.append(s.charAt(j));
                if(i!=0 & i != numRows - 1 && (j-i)+(m-i) < s.length()){
                    sb.append(s.charAt(j-i+m-i));
                }
            }
        }

        return sb.toString();
    }


    public static int lengthOfLongestSubString2(String s){
        if(s == null || s.length() == 0){
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int start=0, end=0, len = 0;
        for(int i =0;i < s.length();i++){
            Character character = s.charAt(i);
            if(map.containsKey(character)){

            }else{
                end++;
            }
            int temp = end - start + 1;
            len = len > temp ? len : temp;
            map.put(character, i);
        }
        return len;
    }

    /**
     *
     * 3. Longest Substring Without Repeating Characters
     * Given a string, find the length of the longest substring without repeating characters.
     *
     * Example 1:
     *
     * Input: "abcabcbb"
     * Output: 3
     * Explanation: The answer is "abc", with the length of 3.
     * Example 2:
     *
     * Input: "bbbbb"
     * Output: 1
     * Explanation: The answer is "b", with the length of 1.
     * Example 3:
     *
     * Input: "pwwkew"
     * Output: 3
     * Explanation: The answer is "wke", with the length of 3.
     *              Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
     *
     *  he basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values,
     *  and keep two pointers which define the max substring. move the right pointer to scan through the string ,
     *  and meanwhile update the hashmap.
     *  If the character is already in the hashmap, then move the left pointer to the right of the same character last found.
     *  Note that the two pointers can only move forward.
     */
    public static int lengthOfLongestSubString(String s){

        if(s == null || s.length() == 0){
            return 0;
        }
        int max = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i =0,j=0; i< s.length();i++){
            if(map.containsKey(s.charAt(i))){
               j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i-j+1);

        }

        /*if(s == null || s.length() == 0){
            return 0;
        }
        int max = 1;
        int start = 0;
        int [] dp = new int[s.length()];
        HashMap<Character, Integer> map = new HashMap<>();
        map.put(s.charAt(0), 0);
        dp[0] = 1;
        for(int i =1;i < s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                dp[i] = dp[i-1] + 1;
                map.put(s.charAt(i), i);
            }else{
                int index = map.get(s.charAt(i));
                if(i == index +1){
                    start = i;
                    dp[i] = 1;
                }
                else if(start > index){
                    dp[i] = dp[i-1] + 1;
                }else if(start == index){
                    dp[i] = i -index;
                }

                map.put(s.charAt(i), i);
            }
            max = max < dp[i] ? dp[i] : max;
        }
        for(int i =0;i < dp.length;i++){
            System.out.print(dp[i] + "  ");
        }
        System.out.println();*/
        return max;
    }


    /**
     *Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.
     *
     * IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;
     *
     * Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.
     *
     * IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).
     *
     * However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.
     *
     * Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.
     *
     * Note: You may assume there is no extra space or special characters in the input string.
     *
     * Example 1:
     * Input: "172.16.254.1"
     *
     * Output: "IPv4"
     *
     * Explanation: This is a valid IPv4 address, return "IPv4".
     * Example 2:
     * Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"
     *
     * Output: "IPv6"
     *
     * Explanation: This is a valid IPv6 address, return "IPv6".
     * Example 3:
     * Input: "256.256.256.256"
     *
     * Output: "Neither"
     *
     * Explanation: This is neither a IPv4 address nor a IPv6 address.
     * @param IP
     * @return
     */
    public static String validIPAddress(String IP) {

        String IPV4 = "IPv4";
        String IPV6 = "IPv6";
        String neither = "Neither";
        if(IP == null
                || IP.length() == 0
                || (!IP.contains(".") && (!IP.contains(":")))
                || (IP.contains(".") && IP.contains(":"))
                || (IP.lastIndexOf(":") == IP.length() -1)
                || (IP.lastIndexOf(".") == IP.length() - 1)){
            return neither;

        }

        String [] ipv4Array = IP.split("\\.");
        if(IP.contains(".") && ipv4Array.length != 4){
            return neither;
        }

        if(isIPV4(ipv4Array)){
            return IPV4;
        }

        String [] ipv6Array = IP.split(":");
        if(IP.contains(":") && ipv6Array.length != 8){
            return neither;
        }

        if(isIPV6(ipv6Array)){
            return IPV6;
        }
        return neither;

    }

    /**
     * IPV6 8组4位16进制组成
     * @param str
     * @return
     */
    public static boolean isIPV6(String [] str){
        for(int i =0; i < str.length;i++){
            String temp = str[i];
            if(temp.length() == 0 || temp.length() > 4){
                return false;
            }
            for(int j =0;j < temp.length();j++){
                char myChar = temp.charAt(j);
                boolean isDigital = myChar >= 48 && myChar <= 57;
                boolean isUpperCase = myChar >= 65 && myChar <= 70;
                boolean isLowerCase = myChar >= 97 && myChar <= 102;
                if(!(isDigital || isLowerCase || isUpperCase)){
                    return false;
                }
            }
        }
        return true;
    }



    /**
     * 判断是否为合法的IPV4
     * @param str
     * @return
     */
    public static boolean isIPV4(String [] str){

        for(int i = 0;i < str.length;i++){
            String temp = str[i];
            try{
                int res = Integer.parseInt(temp);
                if(i == 0 && res == 0 && temp.length() > 1 || (temp.length() != String.valueOf(res).length())){
                    return false;

                }else{
                    if(res > 255 || res <0){
                        return false;
                    }
                }
            }catch (Exception e){
                return false;
            }
        }
        return true;
    }

    /**
     *
     * 97. Interleaving String
     * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
     *
     * Example 1:
     *
     * Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
     * Output: true
     * Example 2:
     *
     * Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
     * Output: false
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave(String s1, String s2, String s3){

        if(s3.length() != s1.length() + s2.length()){

            return false;
        }

        boolean dp[][] = new boolean[s2.length() + 1][s1.length() + 1];
        dp[0][0] = true;

        for(int j =1;j <= s1.length();j++){
            dp[0][j] = (s1.charAt(j-1) == s3.charAt(j-1) ? dp[0][j-1]:false);
        }

        for(int i =1;i <= s2.length();i++){
            dp[i][0] = s2.charAt(i-1) == s3.charAt(i-1) ? dp[i-1][0] : false;
        }

        for(int i =1;i <= s2.length();i++){
            for(int j = 1;j <= s1.length();j++){
                char c = s3.charAt(i+j-1);
                boolean a = c == s1.charAt(j-1) ? dp[i][j-1] : false;

                boolean b = c == s2.charAt(i-1) ? dp[i-1][j] : false;
                dp[i][j] = a||b;
                //System.out.print("dp[" + i + "][" + j + "]=" + dp[i][j] + "   ");
                System.out.print(dp[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println(dp);
        return dp[s2.length()][s1.length()];

    }

    /**
     * 890. Find and Replace Pattern
     *
     * You have a list of words and a pattern, and you want to know which words in words matches the pattern.
     * A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.
     * (Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)
     * Return a list of the words in words that match the given pattern.
     * You may return the answer in any order.
     *
     *
     *
     * Example 1:
     *
     * Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
     * Output: ["mee","aqq"]
     * Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
     * "ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
     * since a and b map to the same letter.
     *
     *
     * Note:
     *
     * 1 <= words.length <= 50
     * 1 <= pattern.length = words[i].length <= 20
     * @param words
     * @param pattern
     * @return
     */
    public static List<String> findAndReplacePattern(String[] words, String pattern) {

        if(pattern == null || words == null || words.length == 0){
           return null;
        }
        List<String> res = new ArrayList<>();
        int [] patternArray = getIndex(pattern);
        for(int i =0;i < words.length;i++){
            int []waitMatch = getIndex(words[i]);
            if(Arrays.equals(patternArray, waitMatch)){
                res.add(words[i]);
            }
        }

        return res;
    }

    public static int[] getIndex(String pattern){

        int [] res = new int [pattern.length()];
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i=0;i < pattern.length();i++){
            map.putIfAbsent(pattern.charAt(i), map.size());
            res[i] = map.get(pattern.charAt(i));
        }
        return res;
    }



    public char findTheDifference(String s, String t) {

        int [] arrays = new int[26];
        for(int i = 0;i < s.length();i++){
            arrays[s.charAt(i) - 'a'] ++;
        }

        for(int j = 0;j < t.length();j++){
            arrays[t.charAt(j) - 'a'] --;
        }
        char res = '0';
        for(int i = 0;i < 26;i++){
            if(arrays[i] < 0){
                res = (char)(i +'a');
                break;
            }
        }
        return res;
    }


    public int firstUniqChar(String s) {

        if(s == null || s.length() <= 0){
            return -1;
        }

        int [] arrays = new int[26];
        for(char c : s.toCharArray()){
            arrays[c - 'a'] ++;
        }

        for(int i = 0;i < s.length();i++){

            if(arrays[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }
        return -1;

    }

}
